首页 > 代码库 > 洛谷 P1144 最短路计数
洛谷 P1144 最短路计数
题目描述
给出一个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。
思路：
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 100003using 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\n"); else printf("%d\n",s[i]); return 0;}
洛谷 P1144 最短路计数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。