最短路计数

/*
    边权值都为1，所以可以用BFS来做
记住 BFS 和 dikstra 都是满足拓扑序性质的，也就是说可以用二者解决图论中的dp问题，而spfa不满足拓扑序的性质
*/


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

const int N=1e6+10,M=4e6+10,P=100003;

int n,m;
int h[N],e[M],ne[M],idx;
int cnt[N],dis[N];
bool st[N];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

/*

   其实st数组是不需要的，因为bfs中每个点第一次入队时的距离是最小的，而我们初始化dis为正无穷，所以如果dis[j]<dis[t]+1，即如果j能被t这个点更新，说明j这个点还没有入过队
*/
/*
   if(dis[j]>dis[t]+1)//第一次被遍历
     {
         dis[j]=dis[t]+1;
         cnt[j]=cnt[t];
         q.push(j);
      }
      else if(dis[j]==dis[t]+1)//被与遍历这个点的同一层的其他点遍历
       cnt[j]=(cnt[j]+cnt[t])%P;
*/
void bfs()
{
    memset(dis,0x3f,sizeof dis);
    queue<int> q;
    dis[1]=0,cnt[1]=1;
    st[1]=true;
    q.push(1);
    
    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(dis[j]==dis[t]+1)//不是第一次遍历了
            cnt[j]=(cnt[j]+cnt[t])%P;
            if(st[j]) continue;
            st[j]=true;
              //第一次被遍历
            dis[j]=dis[t]+1;
            cnt[j]=cnt[t];
            q.push(j);
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    
    memset(h,-1,sizeof h);
    
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b),add(b,a);
    }
    
    bfs();
    
    for(int i=1;i<=n;i++)
    printf("%d\n",cnt[i]);
    
    return 0;
}