最短路计数
Description
给出一个NN个顶点MM条边的无向无权图，顶点编号为1-N1−N。问从顶点11开始，到其他每个点的最短路有几条。
Input
第一行包含22个正整数N,MN,M，为图的顶点数与边数。
接下来MM行，每行22个正整数x,yx,y，表示有一条顶点xx连向顶点yy的边，请注意可能有自环与重边。
output
共NN行，每行一个非负整数，第ii行输出从顶点11到顶点ii有多少条不同的最短路，由于答案有可能会很大，你只需要输出ans mod 100003ansmod100003后的结果即可。如果无法到达顶点ii则输出00。
Examples
Input
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5
Output
1
1
1
2
4
正确解法：
找最短路当然要最短路了啊spfa。
然后就是更新的时候，如果这个点被更新了，那么就是以前的
ans[y]=ans[x]；
如果已经是最短路了，那么就是 ans[y]=ans[y]+ans[x]；
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<map> 6 #include<set> 7 #include<vector> 8 #include<queue> 9 #include<algorithm> 10 #include<cmath> 11 using namespace std; 12 typedef long long ll; 13 const int inf=0x7fffffff; 14 const int N=1000000+10; 15 const int M=2000000+10; 16 const int mod=100003; 17 int T,n,m,w,xx,yy,vv; 18 int Link[N],len=0,bok[N],dis[N],upp[N],que[M],ans[N]; 19 struct student 20 { 21 int y,v,next; 22 }e[M]; 23 void insert(int xx,int yy,int vv) 24 { 25 e[++len].next=Link[xx]; 26 Link[xx]=len; 27 e[len].y=yy; 28 e[len].v=vv; 29 } 30 void init() 31 { 32 memset(e,0,sizeof(e)); 33 memset(Link,0,sizeof(Link)); 34 len=0; 35 scanf("%d %d",&n,&m); 36 while(m--) 37 { 38 scanf("%d %d",&xx,&yy); 39 insert(xx,yy,1); 40 insert(yy,xx,1); 41 } 42 } 43 void print() 44 { 45 for(int i=1;i<=n;i++) 46 printf("%d ",ans[i]); 47 } 48 void spfa() 49 { 50 memset(upp,0,sizeof(upp)); 51 memset(bok,0,sizeof(bok)); 52 memset(que,0,sizeof(que)); 53 for(int i=1;i<=n;i++) 54 dis[i]=inf; 55 int head=1,tail=2; 56 dis[1]=0; 57 que[1]=1; 58 bok[1]=1; 59 ans[1]=1; 60 while(head<tail) 61 { 62 int tt=que[head]; 63 bok[tt]=0; 64 for(int i=Link[tt];i;i=e[i].next) 65 { 66 if(dis[e[i].y]>dis[tt]+e[i].v) 67 { 68 dis[e[i].y]=dis[tt]+e[i].v; 69 ans[e[i].y]=ans[tt]; 70 if(bok[e[i].y]==0) 71 { 72 que[tail++]=e[i].y; 73 bok[e[i].y]=1; 74 } 75 } 76 else if(dis[e[i].y]==dis[tt]+e[i].v) 77 { 78 ans[e[i].y]+=ans[tt]; 79 ans[e[i].y]%=mod; 80 } 81 } 82 head++; 83 } 84 } 85 int main() 86 { 87 init(); 88 spfa(); 89 print(); 90 91 return 0; 92 }