单源最短路径（SPFA）

单源最短路径

题目背景
本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入格式
第一行包含三个整数 n,m,s分别表示点的个数、有向边的个数、出发点的编号。
接下来 m 行每行包含三个整数 u,v,w表示一条 u→v的，长度为 w 的边。
输出格式
输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 2^31−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
样例说明：
图片1到3和1到4的文字位置调换
分析
这题我们可以用SPFA的队列模板
可以参考香甜的黄油（SPFA）
AC代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
int n,m,s,x,y,z,x1,tot,hd[1000005],v[100005],f[100005],d[100005];//定大点
struct stu
{
	int to,next,w;
}a[1000005];
void add(int x,int y,int z)//邻接表建立
{
	tot++;
	a[tot].to=y;
	a[tot].w=z;
	a[tot].next=hd[x];
	hd[x]=tot;
}
void spfa(int x)
{
	d[x]=0,v[x]=1;
	queue<int>f;//队列建立
	f.push(x);//入队
	while(!f.empty())//判断队列是否为空
	{
		x1=f.front();//取队首
		f.pop();//弹出队首
		for(int j=hd[x1];j;j=a[j].next)
		 if(d[a[j].to]>d[x1]+a[j].w)//松弛
		  {
			d[a[j].to]=d[x1]+a[j].w;
			if(v[a[j].to]==0)
			{
				v[x1]=1;
				f.push(a[j].to);
			}
		 }
		v[x1]=0;
	} 
}
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);//有向图
	}
	for(int i=1;i<=n;i++)d[i]=2147483647;//赋值
	spfa(s);//用这个点去找
	for(int i=1;i<=n;i++)cout<<d[i]<<' ';
}

谢谢