（洛谷 1144）最短路计数#spfa#

本文主要是介绍（洛谷 1144）最短路计数#spfa#，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

求最短路的个数

---

分析

用spfa求答案，在dis松弛的情况下同时求答案

---

代码

#include <cstdio>
using namespace std;
struct q{int x,y,w,next;
}a[2000001]; int go=0;
int n,m,l,d[1000001],ans[1000001],t,list[1000001],ls[1000001];
bool v[1000001];
void spfa(int st){int head=0,tail=1;for (int i=1;i<=n;i++) d[i]=2147483647;list[1]=st; v[st]=ans[st]=1; d[st]=0;do{head++;if (head>n) head=1;t=ls[list[head]];while (t>0){if (d[a[t].x]+1<d[a[t].y]){d[a[t].y]=d[a[t].x]+1;ans[a[t].y]=ans[a[t].x];//更新最短路条数if (!v[a[t].y]){v[a[t].y]=1;tail++;if (tail>n) tail=1;list[tail]=a[t].y;}}//因为更新了数据，所以最短路=之前的点的最短路else if (d[a[t].x]+1==d[a[t].y])ans[a[t].y]=(ans[a[t].y]+ans[a[t].x])%100003;//从上一个点直接通向这个点，说明最短路是必须包含的t=a[t].next;}v[list[head]]=0;}while (head!=tail);//循环队列的bugfor (int i=1;i<=n;i++) printf("%d\n",ans[i]);
}
int main(){scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);a[++go].x=u; a[go].y=v; a[go].next=ls[u]; ls[u]=go;a[++go].x=v; a[go].y=u; a[go].next=ls[v]; ls[v]=go;} spfa(1);
}

这篇关于（洛谷 1144）最短路计数#spfa#的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---