（洛谷 3371）【模（mú）板】单源最短路径#spfa#

本文主要是介绍（洛谷 3371）【模（mú）板】单源最短路径#spfa#，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

求单源最短路径

分析

spfa来一波

代码

#include <cstdio>
using namespace std;
struct q{int x,y,w,next;
}a[500001];
int n,m,l,d[500001],t,list[500001],ls[500001];
bool v[500001];
void spfa(int st){int head=0,tail=1;for (int i=1;i<=n;i++) d[i]=2147483647;list[1]=st; v[st]=1; d[st]=0;do{head++;//if (head>n) head=1;t=ls[list[head]];while (t>0){if (d[a[t].x]+a[t].w<d[a[t].y]){d[a[t].y]=d[a[t].x]+a[t].w;//松弛算法if (!v[a[t].y]){v[a[t].y]=1;//访问成功tail++;//if (tail>n) tail=1;list[tail]=a[t].y;}}t=a[t].next;//下一个}v[list[head]]=0;//避免最优值被覆盖}while (head<tail);for (int i=1;i<=n;i++) printf("%d ",d[i]);
}
int main(){scanf("%d%d%d",&n,&m,&l);for (int i=1;i<=m;i++){scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);a[i].next=ls[a[i].x];//邻接链表ls[a[i].x]=i;//邻接链表（有向图）} spfa(l);
}

然后是循环队列

#include <cstdio>
using namespace std;
struct q{int x,y,w,next;
}a[500001];
int n,m,l,d[10001],t,list[10001],ls[10001];
bool v[10001];
void spfa(int st){int head=0,tail=1;for (int i=1;i<=n;i++) d[i]=2147483647;list[1]=st; v[st]=1; d[st]=0;do{head++;if (head>n) head=1;t=ls[list[head]];while (t>0){if (d[a[t].x]+a[t].w<d[a[t].y]){d[a[t].y]=d[a[t].x]+a[t].w;if (!v[a[t].y]){v[a[t].y]=1;tail++;if (tail>n) tail=1;list[tail]=a[t].y;}}t=a[t].next;}v[list[head]]=0;}while (head!=tail);//（一定要是不相同而不是小于，因为是循环队列，n次WA）for (int i=1;i<=n;i++) printf("%d ",d[i]);
}
int main(){scanf("%d%d%d",&n,&m,&l);for (int i=1;i<=m;i++){scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);a[i].next=ls[a[i].x];ls[a[i].x]=i;} spfa(l);
}