首页 > 代码库 > 【SPFA】 最短路计数
【SPFA】 最短路计数
最短路计数
【问题描述】
给出一个N个顶点M条边的无向无权图，顶点编号为1～N。问从顶点1开始，到其他每个点的最短路有几条。
【输入格式】
输入第一行包含2个正整数N，M，为图的顶点数与边数。
接下来M行，每行两个正整数x, y，表示有一条顶点x连向顶点y的边，请注意可能有自环与重边。
【输出格式】
输出包括N行，每行一个非负整数，第i行输出从顶点1到顶点i有多少条不同的最短路，由于答案有可能会很大，你只需要输出mod 100003后的结果即可。如果无法到达顶点i则输出0。
【输入样例】
5 71 21 32 43 42 34 54 5
【输出样例】
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 ≤ 100000，M ≤ 200000。
【试题分析】
非常显然，因为上午学了SPFA，准备找一题练练手……
邻接表秒过，主要老是有个BUG
还好吃了顿饭就醒悟了……
SPFA一遍就行了。
【代码】
#include<iostream>#include<cstring>#include<cstdio>using namespace std;int cnt=0;int Root[400002],Node[400002],Next[400002];int que[400002],dis[400002];bool vis[400002];int ans[400002];int N,M;void add(int u,int v,int w){//邻接表存储 cnt++; Node[cnt]=v; Next[cnt]=Root[u]; Root[u]=cnt;}void SPFA(int s){ memset(vis,false,sizeof(vis)); for (int i=1; i<=N; i++) dis[i]=9999999; memset(que,0,sizeof(que)); int tail=1; que[tail]=s; dis[s]=0; ans[1]=1; vis[s]=true; for(int head=1;head<=tail;head++){ for(int x=Root[que[head]];x!=0;x=Next[x]){ if(dis[que[head]]+1<dis[Node[x]]){ dis[Node[x]]=dis[que[head]]+1; ans[Node[x]]=ans[que[head]]%100003; if(vis[Node[x]]==false){ que[++tail]=Node[x]; vis[Node[x]]=true; } } else if(dis[que[head]]+1==dis[Node[x]]) ans[Node[x]]=(ans[Node[x]]+ans[que[head]])%100003;//等于就更新答案 } vis[Node[head]]=false; }}int main(){ cin>>N>>M; for(int i=0;i<M;i++){ int u,v,w=1; scanf("%d%d",&u,&v); add(u,v,w);//由于我们要存的是双向图，所以注意要储存两次 add(v,u,w);//注意数组开两倍 } SPFA(1); for(int i=1;i<=N;i++) cout<<ans[i]<<endl;//输出}
【SPFA】 最短路计数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。