题目描述
给出一个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。
思路：
s[i]记录到i节点的最短路的数量，如果有从x到y节点所需长度比当前的小，则s[y]=s[x]；
如果有一种从x点更新比当前到点y所需长度相等的方案那么s[y]+=s[x]；
s[]初始值为1。
代码：
#include<cstdio> #include<queue> #define maxn 1000001 #define mod 100003 using namespace std; int n,m,head[maxn],tot,v[maxn],s[maxn]; bool vis[maxn]; queue<int>q; struct node { int to,next,w; }a[maxn*2]; void add(int x,int y,int z) { tot++; a[tot].to=y; a[tot].next=head[x]; a[tot].w=z; head[x]=tot; } void spfa() { v[1]=0; vis[1]=1; s[1]=1; q.push(1); while(!q.empty()) { int x=q.front(); q.pop(); vis[x]=0; for(int i=head[x];i;i=a[i].next) { int y=a[i].to; if(v[y]==v[x]+a[i].w) s[y]=(s[x]+s[y])%mod; else if(v[y]>v[x]+a[i].w) { s[y]=s[x]%mod,v[y]=v[x]+a[i].w; if(!vis[y]) vis[y]=1,q.push(y); } } } } int main() { int i,j,x,y,z; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) scanf("%d%d",&x,&y),add(x,y,1),add(y,x,1); for(i=1;i<=n;i++) v[i]=123456789; spfa(); for(i=1;i<=n;i++) if(v[i]==123456789) printf("0 "); else printf("%d ",s[i]); return 0; }