传送门 题解：先跑一遍SPFA，然后再dp，如果dis[v]+1==dis[p]，则有ans[p]=(ans[p]+ans[v])%MOD 注意：ans[1]初始化为1（1的最短路就是0，有一条），否则ans跑出来全是0……
#include<bits/stdc++.h> using namespace std; const int MAXN=1e6+2,MAXM=2e6+2,MOD=1e5+3; int n,m,head[MAXN],edge=0; struct EDGE { int v,nxt; }e[MAXM<<1]; bool vis[MAXN]; int dis[MAXN],ans[MAXN]; inline int read() { int x=0;char c=getchar(); while (c<'0'||c>'9') c=getchar(); while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x; } inline void adde(int u,int v) { e[edge].nxt=head[u],e[edge].v=v,head[u]=edge++; e[edge].nxt=head[v],e[edge].v=u,head[v]=edge++; } inline void SPFA() { queue<int> q; memset(vis,false,sizeof(vis)); memset(dis,0x3f,sizeof(dis)),dis[1]=0; q.push(1),vis[1]=true; while (!q.empty()) { int p=q.front(); q.pop(),vis[p]=false; for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; if (dis[v]>dis[p]+1) { dis[v]=dis[p]+1; if (!vis[v]) { vis[v]=true; q.push(v); } } } } } int cal(int p) { for (int i=head[p];~i;i=e[i].nxt) { int v=e[i].v; if (dis[v]+1==dis[p]) { if (!ans[v]) ans[v]=cal(v); ans[p]=(ans[p]+ans[v])%MOD; } } return ans[p]; } int main() { // freopen("P1144.in","r",stdin); memset(head,-1,sizeof(head)); n=read(),m=read(); for (register int i=0;i<m;++i) { int u=read(),v=read(); adde(u,v); } SPFA(); memset(ans,0,sizeof(ans)),ans[1]=1; for (register int i=1;i<=n;++i) { if (!ans[i]) ans[i]=cal(i); printf("%d\n",ans[i]); } return 0; }