题目描述
给出一个N个顶点M条边的无向无权图，顶点编号为1～N。问从顶点1开始，到其他每个点的最短路有几条。
输入输出格式
输入格式：
输入第一行包含2个正整数N，M，为图的顶点数与边数。
接下来M行，每行两个正整数x, y，表示有一条顶点x连向顶点y的边，请注意可能有自环与重边。
输出格式：
输出包括N行，每行一个非负整数，第i行输出从顶点1到顶点i有多少条不同的最短路，由于答案有可能会很大，你只需要输出mod 100003后的结果即可。如果无法到达顶点i则输出0。
输入输出样例
输入样例#1：
5 7 1 2 1 3 2 4 3 4 2 3 4 5 4 5
输出样例#1：
1 1 1 2 4
说明
1到5的最短路有4条，分别为2条1-2-4-5和2条1-3-4-5（由于4-5的边有2条）。
对于20%的数据，N ≤ 100；
对于60%的数据，N ≤ 1000；
对于100%的数据，N<=1000000，M<=2000000。
代码:
1 #include<cstdio> 2 using namespace std; 3 const int mod=100003,N=1000005,M=2000005; 4 const int INF=1e9+10; 5 6 int n,m,cnt,H[M<<1],Dist[N],Sum[N],que[mod+10]; 7 bool vis[N]; 8 struct Edge 9 { 10 int to,nxt; 11 }e[M<<1]; 12 13 void read(int &now) 14 { 15 now=0;char c=getchar(); 16 while(c<'0'||c>'9')c=getchar(); 17 while(c>='0'&&c<='9')now=(now<<3)+(now<<1)+c-'0',c=getchar(); 18 } 19 20 void AddEdge(int u,int v) 21 { 22 e[++cnt].to = v; 23 e[cnt].nxt = H[u]; 24 // e[cnt].val = w; 25 H[u] = cnt; 26 } 27 28 void spfa() 29 { 30 for(int i=1;i<=n;++i) 31 Dist[i]=INF; 32 Dist[1]=0;Sum[1]=1;vis[1]=1; 33 int h=0,t=1; 34 que[h]=1; 35 while(h<t) 36 { 37 int cur=que[h++]; 38 h=(h-1)%mod+1; 39 vis[cur]=0; 40 for(int i=H[cur];i;i=e[i].nxt) 41 { 42 int to=e[i].to; 43 if(Dist[cur]+1==Dist[to]) 44 Sum[to]=(Sum[cur]+Sum[to])%mod;//到to的路径数加上到cur的路径数 45 else if(Dist[cur]+1<Dist[to]) 46 { 47 Dist[to]=Dist[cur]+1; 48 Sum[to]=Sum[cur]; 49 if(!vis[to]) 50 que[t++]=to,t=(t-1)%mod+1,vis[to]=1; 51 } 52 } 53 } 54 } 55 56 int main() 57 { 58 read(n);read(m); 59 int x,y; 60 while(m--) 61 { 62 read(x);read(y); 63 AddEdge(x,y);//AddEdge(x,y,1); 64 AddEdge(y,x); 65 } 66 spfa(); 67 for(int i=1;i<=n;++i) 68 if(Dist[i]==INF) 69 printf("0 "); 70 else 71 printf("%d ",Sum[i]); 72 return 0; 73 }