首页 > 代码库 > 洛谷——P1144 最短路计数
洛谷——P1144 最短路计数
https://www.luogu.org/problem/show?pid=1144#sub
题目描述
给出一个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 <algorithm> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 6 using namespace std; 7 8 const int mod(100003); 9 const int N(1000000+15);10 const int M(2000000+15);11 int n,m,u,v,w;12 13 int head[N],sumedge;14 struct Edge15 {16 int u,v,next;17 Edge(int u=0,int v=0,int next=0):18 u(u),v(v),next(next){}19 }edge[M<<1];20 void ins(int u,int v)21 {22 edge[++sumedge]=Edge(u,v,head[u]);23 head[u]=sumedge;24 }25 26 queue<int>que;27 int dis[N],cnt[N],inq[N];28 void SPFA()29 {30 for(int i=1;i<=n;i++) dis[i]=N*10;31 que.push(1); inq[1]=1; dis[1]=0; cnt[1]=1;32 for(int fro;!que.empty();)33 {34 fro=que.front();que.pop();inq[fro]=0;35 if(fro==n) continue;36 for(int i=head[fro];i;i=edge[i].next)37 {38 int v=edge[i].v;39 if(dis[v]==dis[fro]+1)40 cnt[v]=(cnt[v]%mod+cnt[fro]%mod)%mod;41 else if(dis[v]>dis[fro]+1)42 {43 dis[v]=dis[fro]+1;44 cnt[v]=cnt[fro]%mod;45 if(!inq[v]) que.push(v),inq[v]=1;46 }47 }48 }49 }50 51 int main()52 {53 scanf("%d%d",&n,&m);54 for(int i=1;i<=m;i++)55 {56 scanf("%d%d",&u,&v);57 ins(u,v);ins(v,u);58 }59 SPFA();60 for(int i=1;i<=n;i++) printf("%d\n",cnt[i]);61 return 0;62 }
洛谷——P1144 最短路计数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。