首页 > 代码库 > 洛谷P1144 最短路计数（SPFA）
洛谷P1144 最短路计数（SPFA）
To 洛谷.1144 最短路计数
题目描述
给出一个N个顶点M条边的无向无权图，顶点编号为1～N。问从顶点1开始，到其他每个点的最短路有几条。
输入输出格式
输入格式：
输入第一行包含2个正整数N，M，为图的顶点数与边数。
接下来M行，每行两个正整数x, y，表示有一条顶点x连向顶点y的边，请注意可能有自环与重边。
输出格式：
输出包括N行，每行一个非负整数，第i行输出从顶点1到顶点i有多少条不同的最短路，由于答案有可能会很大，你只需要输出mod 100003后的结果即可。如果无法到达顶点i则输出0。
输入输出样例
输入样例#1：
5 71 21 32 43 42 34 54 5
输出样例#1：
11124
说明
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\n");70 else71 printf("%d\n",Sum[i]);72 return 0;73 }
洛谷P1144 最短路计数（SPFA）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。