莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 这就一道简单bfs求解最短路方案数的问题
2. 先求出到达各点的最短路，再统计各个最短路的方案数

#include<bits/stdc++.h>

using namespace std;

const int N = 100010, M = 400010, mod = 100003;

int n,m;
int h[N],e[M],ne[M],idx;
int dist[N],cnt[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void bfs()
{
    //初始化dist数组
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    //初始化队列q
    queue<int> q;
    q.push(1);

    //初始化cnt数组
    cnt[1]=1;

    while(q.size())
    {
        //取出队头
        auto t=q.front();
        q.pop();

        //枚举该点的所有出边
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];

            //有更小的路可以更新
            if(dist[j]>dist[t]+1)
            {
                dist[j]=dist[t]+1;
                q.push(j);
            }

            //跟到该点的最短路相等
            if(dist[j]==dist[t]+1) cnt[j]=(cnt[j]+cnt[t])%mod;
        }
    }
}

int main()
{
    cin>>n>>m;

    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }

    bfs();

    for(int i=1;i<=n;i++) cout<<cnt[i]<<endl;

    return 0;
}