1.無權圖最短路邊權為1
2.如果兩個點恰好不能被更新（d[y]==d[x]+1）那麼就能通過x的所有最短路到達y，所以ans[y]+=ans[x]
3.如果兩個點不能恰好被更新（d[y]>d[x]+1）那麼到達y的最短路目前只有通過x到達，所以ans[y]=ans[x]
#include#include #include #include using namespace std;const int maxn=1000010;const int maxm=2000010;const int mod=100003;int n,m;int head[maxn],cnt;struct node{ int v,nxt;}e[maxn*2];void add(int u,int v){ e[++cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt;}queue q;int d[maxn],v[maxn],c[maxn];void spfa(){ d[1]=0;v[1]=1;q.push(1); c[1]=1;//初值 while(!q.empty()){ int x=q.front();q.pop();v[x]=0; for(int i=head[x];i;i=e[i].nxt){ int y=e[i].v; if(d[y]>d[x]+1){ d[y]=d[x]+1; c[y]=c[x];//覆蓋 if(!v[y])q.push(y),v[y]=1; } else if(d[y]==d[x]+1)c[y]+=c[x],c[y]%=mod;//相等就合併 } }}int main(){ scanf("%d%d",&n,&m); for(int i=1,x,y;i<=m;i++){ scanf("%d%d",&x,&y); add(x,y);add(y,x); } memset(d,0x3f,sizeof(d)); spfa(); for(int i=1;i<=n;i++)printf("%d\n",c[i]);}