题目描述 给出一个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 7 1 2 1 3 2 4 3 4 2 3 4 5 4 5 输出 #1 复制 1 1 1 2 4 说明/提示 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。 用spfa求最短路，然后记录有多少个相同的到该点的最短路。 代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 1000000; vector<int>E[maxn]; int n,m,u,v; int d[maxn],inq[maxn]; int ans[maxn]; void init() { for(int i=0;i<maxn;i++) { E[i].clear(); } for(int i=0;i<maxn;i++) { inq[i]=0; } for(int i=0;i<maxn;i++) { d[i]=1e9; } } void spfa(int root) { queue<int> q; q.push(root); ans[root]=1,d[root]=0,inq[root]=1; while(!q.empty()) { int now = q.front(); q.pop(); for(int i=0;i<E[now].size();i++) { v=E[now][i]; if(d[v]>d[now]+1) { d[v]=d[now]+1; ans[v]=ans[u]; if(inq[v]==0) { inq[v]=1; q.push(v); } } if(d[v]==d[now]+1) { ans[v] = (ans[v] + ans[now]) % 100003; } } inq[now]=0; } } int main() { cin>>n>>m; init(); while(m--) { cin>>u>>v; E[u].push_back(v); E[v].push_back(u); } spfa(1); for(int i = 1; i <= n; i++) cout << ans[i] << endl; return 0; }