本文主要是介绍【洛谷P3371】【模板】单源最短路径（弱化版），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【模板】单源最短路径（弱化版）
题目链接：【模板】单源最短路径（弱化版）
题目背景
本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入格式
第一行包含三个整数 n,m,sn,m,sn,m,s，分别表示点的个数、有向边的个数、出发点的编号。
接下来 mmm 行每行包含三个整数 u,v,wu,v,wu,v,w，表示一条u→v的，长度为w的边。
输出格式
输出一行 nnn 个整数，第 iii 个表示 sss 到第 iii 个点的最短路径，若不能到达则输出 231−12^{31}-1231−1。
输入输出样例
输入
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出
0 2 4 3
解题思路
金典SPAF
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long n,p,c,a[81000],b[810000][5];
long long ans[81000],m,d[81000];
long long tot,head[100000];
long long f[10000100],maxn;
void add(int x,int y,int k)
{tot++;b[tot][1]=x;b[tot][2]=y;b[tot][3]=k;b[tot][4]=head[x];head[x]=tot;
}
int main()
{cin>>maxn>>c>>n;for(int i=1;i<=c;i++){int x,y,k;scanf("%d%d%d",&x,&y,&k);add(x,y,k);}for(int i=1;i<=maxn;i++){ans[i]=2147483647;}memset(d,0,sizeof(d));int hd=0,tl=1;f[1]=n;d[n]=1;ans[n]=0;while(hd<=tl){hd++;int x1=f[hd];for(int j=head[x1];j;j=b[j][4])if(ans[b[j][2]]>ans[x1]+b[j][3]){ans[b[j][2]]=ans[x1]+b[j][3];if(d[b[j][2]]==0){tl++;d[x1]=1;f[tl]=b[j][2];}}d[x1]=0;}for(int j=1;j<=maxn;j++)cout<<ans[j]<<" ";
}
这篇关于【洛谷P3371】【模板】单源最短路径（弱化版）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
