题目描述
给出一个N个顶点M条边的无向无权图，顶点编号为1-N。问从顶点11开始，到其他每个点的最短路有几条。
输入输出格式
输入格式：
第一行包含2个正整数N,M为图的顶点数与边数。
接下来M行，每行22个正整数x,y,表示有一条顶点x连向顶点y的边，请注意可能有自环与重边。
输出格式：
共N行，每行一个非负整数，第ii行输出从顶点11到顶点ii有多少条不同的最短路，由于答案有可能会很大，你只需要输出ans \bmod 100003ansmod100003后的结果即可。如果无法到达顶点ii则输出0。
思路：
跑最短路的同时维护一下答案就行，如果d[y]=d[x]+1,就把ans[y]+=ans[x],否则在更新d[y]时令ans[y]=ans[x];
代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 inline int read() 9 { 10 char ch=getchar(); 11 int x=0,f=1; 12 while((ch>‘9‘||ch<‘0‘)&&ch!=‘-‘) 13 ch=getchar(); 14 if(ch==‘-‘) 15 { 16 f=-1; 17 ch=getchar(); 18 } 19 while(‘0‘<=ch&&ch<=‘9‘) 20 { 21 x=x*10+ch-‘0‘; 22 ch=getchar(); 23 } 24 return x*f; 25 } 26 int mod=100003; 27 int n,m,x,y,tot=0; 28 const int N=1000005,M=4000005; 29 int head[N],to[M],nxt[M],d[N],ans[N]; 30 bool p[N]; 31 queue< int > q; 32 void add(int x,int y) 33 { 34 to[++tot]=y; 35 nxt[tot]=head[x]; 36 head[x]=tot; 37 } 38 int main() 39 { 40 n=read();m=read(); 41 for(int i=1;i<=m;i++) 42 { 43 x=read();y=read(); 44 add(x,y); 45 add(y,x); 46 } 47 for(int i=1;i<=n;i++) 48 { 49 d[i]=1e9;p[i]=0; 50 } 51 d[1]=0; 52 p[1]=1; 53 ans[1]=1; 54 q.push(1); 55 while(q.size()) 56 { 57 x=q.front();q.pop(); 58 p[x]=0; 59 for(int i=head[x];i;i=nxt[i]) 60 { 61 y=to[i]; 62 if(d[y]>d[x]+1) 63 { 64 d[y]=d[x]+1; 65 ans[y]=ans[x]; 66 if(!p[y]) 67 { 68 q.push(y); 69 p[y]=1; 70 } 71 } 72 else if(d[y]==d[x]+1) 73 { 74 ans[y]+=ans[x]; 75 ans[y]%=mod; 76 } 77 } 78 } 79 for(int i=1;i<=n;i++) 80 printf("%d\n",ans[i]); 81 return 0; 82 }
原文：https://www.cnblogs.com/wmq12138/p/10351255.html
