思路

单源最短路，本题可以使用bfs来解决，只需要将板子稍加修改即可。

我们设 $pa_i$ 为点 $1$ 到 $i$ 的最短路长度，初始 $pa_i=\begin{cases}0,\,i=1\\\infty,\,i>1\end{cases}$

设 $cnt_i$ 为最短路条数，初始 $cnt_i=\begin{cases}1,\,i=1\\0,\,i>1\end{cases}$

如果当前遍历到的节点为 $i$，它的上一个节点为 $x$，那么：

• 如果 $pa_i>pa_x+1$，说明点 $i$ 之前没有被遍历过，那么我们令 $pa_i=pa_x+1$，$cnt_i=cnt_x$；
• 如果 $pa_i=pa_x+1$，说明最短路长度相同（存在环），那么我们令 $cnt_i=cnt_i+cnt_x$，加上取模就是 $cnt_i=(cnt_i+cnt_x)\mod 100003$。

这其实也是应用了动态规划的思想。

AC Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+5,MOD=100003;
ll n,m,pa[N],cnt[N];
vector<ll> vec[N];
queue<ll> q;
int main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1,u,v;i<=m;i++)
        scanf("%lld%lld",&u,&v),vec[u].push_back(v),vec[v].push_back(u);
    // 初始化数组
    memset(pa,0x3f,sizeof(pa));
    pa[1]=0,cnt[1]=1; 
    q.push(1); // 将初始点加入队列
    while(!q.empty()){
        ll x=q.front();
        q.pop();
        for(auto i=vec[x].begin();i!=vec[x].end();i++)
            // 按照上述思路判断
            if(pa[*i]>pa[x]+1){
                pa[*i]=pa[x]+1;
                cnt[*i]=cnt[x];
                q.push(*i);
            }else if(pa[*i]==pa[x]+1)
                cnt[*i]=(cnt[*i]+cnt[x])%MOD;
    }
    for(ll i=1;i<=n;i++)
        printf("%lld\n",cnt[i]);
    return 0;
}