如有乱码，请。

 

 

题目描述

给出一个NN个顶点MM条边的无向无权图，顶点编号为1-N1−N。问从顶点11开始，到其他每个点的最短路有几条。

输入格式

第一行包含22个正整数N,MN,M，为图的顶点数与边数。

接下来MM行，每行22个正整数x,yx,y，表示有一条顶点xx连向顶点yy的边，请注意可能有自环与重边。

输出格式

共NN行，每行一个非负整数，第ii行输出从顶点11到顶点ii有多少条不同的最短路，由于答案有可能会很大，你只需要输出ans \bmod 100003ansmod100003后的结果即可。如果无法到达顶点ii则输出00。

输入输出样例

输入 #1复制

5 71 21 32 43 42 34 54 5

输出 #1复制

11124

说明/提示

11到55的最短路有44条，分别为22条1-2-4-51−2−4−5和22条1-3-4-51−3−4−5（由于4-54−5的边有22条）。

对于20\%20%的数据，N ≤ 100N≤100；

对于60\%60%的数据，N ≤ 1000N≤1000；

对于100\%100%的数据，N<=1000000,M<=2000000N<=1000000,M<=2000000。

 

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int read(){ int a=0,b=1; char ch=getchar(); while((ch<48||ch>57)&&ch!='-'){ ch=getchar(); } if(ch=='-'){ b=-1; ch=getchar(); } while(ch<48||ch>57){ ch=getchar(); } while(ch>47&&ch<58){ a=a*10+ch-48; ch=getchar(); } return a*b;}int n,m,x,y,tot=0;int head[1000005],to[4000005],nxt[4000005],d[1000005],ans[1000005];bool p[1000005];priority_queue< pair< int,int > > q;void add(int x,int y){ to[++tot]=y; nxt[tot]=head[x]; head[x]=tot;}int main(){ n=read(); m=read(); for(int i=1;i<=m;i++){ x=read(); y=read(); add(x,y); add(y,x); } for(int i=1;i<=n;i++){ d[i]=1e9; p[i]=0; } d[1]=0; ans[1]=1; q.push(make_pair(0,1)); while(q.size()){ x=q.top().second; q.pop(); if(p[x]){continue;} p[x]=1; for(int i=head[x];i;i=nxt[i]){ y=to[i]; if(d[y]>d[x]+1){ d[y]=d[x]+1; ans[y]=ans[x]; q.push(make_pair(-d[y],y)); } else if(d[y]==d[x]+1){ ans[y]+=ans[x]; ans[y]%=100003; } } } for(int i=1;i<=n;i++){ printf("%d\n",ans[i]); } return 0;}