P1144 最短路计数 • CoderXL's Blog

非常好 BFS 板子。

由于边的长度均为 $1$ ，因此 BFS 遍历的顺序一定是由近及远的。不可能出现后遍历到的点比先前遍历到的点更近。因此，每个点在第一次进入队列时，其最短距离就已经被找到了。这个性质的一个好处是：同一个点只需要入队一次，因为后续到达该点的路径长度不可能小于第一次入队时的长度。

这允许我们确保时间复杂度为 $O(n+m)$ ，队列的空间复杂度为 $O(n)$ ，整体空间复杂度为 $O(n+m)$ .

以下列出两种等效写法：

写法 1：

#include <bits/stdc++.h>
using namespace std;

const int N = 1000010, M = 2000010, Mod = 100003;

int n,m;
int dis[N];
int ans[N];
vector<int> edge[N];
queue<int>q;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    q.push(1);
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    ans[1]=1;
    while(!q.empty())
    {
        auto h=q.front();q.pop();
        for(const auto&y:edge[h])
        {
            if(dis[y]>dis[h]+1)
            {
                q.push(y);
                dis[y]=dis[h]+1;
            }
            if(dis[y]==dis[h]+1)
            {
                ans[y]+=ans[h];
                ans[y]%=Mod;
            }
        }
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
    return 0;
}

cpp

写法 2：

    q.push(1);
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    entered_queue[1]=true;
    ans[1]=1;
    while(!q.empty())
    {
        auto h=q.front();q.pop();
        for(const auto&y:edge[h])
        {
            if(dis[y]>dis[h]+1)
            if(!entered_queue[y])
            {
                q.push(y);
                entered_queue[y]=true;
                dis[y]=dis[h]+1;
            }
            if(dis[y]==dis[h]+1)
            {
                ans[y]+=ans[h];
                ans[y]%=Mod;
            }
        }
    }

cpp

以下是一种错误写法，会导致 TLE MLE 和 WA，可以思考一下为什么：

    q.push(1);
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    entered_queue[1]=true;
    ans[1]=1;
    while(!q.empty())
    {
        auto h=q.front();q.pop();
        for(const auto&y:edge[h])
        {
            if(dis[y]>dis[h]+1)
            if(dis[y]>=dis[h]+1)
            {
                q.push(y);
                entered_queue[y]=true;
                dis[y]=dis[h]+1;
            }
            if(dis[y]==dis[h]+1)
            {
                ans[y]+=ans[h];
                ans[y]%=Mod;
            }
        }
    }

cpp