#10077. 「一本通 3.2 练习 3」最短路计数

问1~n的最短路有几个

#include <iostream>
#include <cstring>
#include <queue>
using namespace std ; 
 const int N=1e6+2,M=2e6+2;
  const int inf=0x3f3f3f3f,mod=100003;
 int all,nxt[M],go[M],hd[N];
 int dis[N],vis[N],n,m;
 
 int cnt[N];
 void add(int x,int y){
     go[++all]=y; nxt[all]=hd[x],hd[x]=all;
 }
 
 void spfa(int v0){
     int i,x,y;
     queue<int> q;
     memset(vis,0,sizeof vis);
     for(i=1;i<=n;i++) dis[i]=inf; dis[v0]=0;
     cnt[v0]=1;
     q.push(v0); vis[v0]=1;
     
     while(!q.empty()){
         x=q.front(),q.pop();
         vis[x]=0;
         
         for(i=hd[x];i;i=nxt[i]){
             y=go[i];
             if(dis[y]>dis[x]+1){
                  dis[y]=dis[x]+1;
                  cnt[y]=cnt[x];
                  if(!vis[y]) vis[y]=1,q.push(y);
             }
             else if(dis[y]==dis[x]+1){
                 cnt[y]+=cnt[x];cnt[y]%=mod;
             }
        }
     }
 }
 signed main(){
     int i,x,y;
    scanf("%d%d",&n,&m);
     for(i=1;i<=m;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
      
    spfa(1);
    for(i=1;i<=n;i++) cout<<cnt[i]<<endl;
 }