本文共 1308 字，大约阅读时间需要 4 分钟。

题目背景

本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

第一行包含三个整数$n,m,s$，分别表示点的个数、有向边的个数、出发点的编号。

接下来 mmm 行每行包含三个整数 $u,v,w$，表示一条 $u\to v$ 的，长度为 www 的边。

输出一行 $n$ 个整数，第 $i$ 个表示 $s$ 到第 $i$ 个点的最短路径，若不能到达则输出 $2^{31}-1$。

4 6 11 2 22 3 22 4 11 3 53 4 31 4 4

输出 #1

0 2 4 3

说明/提示

【数据范围】

对于真正 $100\%$ 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。

样例说明：

图片1到3和1到4的文字位置调换

解题思路

模板

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int maxn=0x7fffffff;struct DT{   	int to,l,next;}a[600000];int dis[20000],head[20000],n,m,k,num;queue
       
         v;int h,t,f[20000];void SPFA(int s){   	memset(dis,0x7f,sizeof(dis));	v.push(s);	h=0,t=1,dis[s]=0,f[s]=1;	while(!v.empty()){   		for(int i=head[v.front()];i;i=a[i].next){   			if(dis[v.front()]+a[i].l