题目描述

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

输入格式

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

接下来 $m$ 行每行包含三个整数 $u,v,w$，表示一条 $u \to 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 \le n \le 10^4$

$1 \le m \le 5\times10^5$

$0 \lt w \le 1000$

提示

数据为随机数据。对于随机数据，SPFA 的时间复杂度为 O(m)；如果数据不是随机的，在特殊情况下，SPFA 的时间复杂度会达到 O(V*E)，和 Bellman-Ford 的计算复杂度一致。

完成程序

#include<bits/stdc++.h>
using namespace std;
const int maxn=10001;
const int maxm=500001;
int n,m,s,e_id,h[maxn];

struct Edge{
	int v,w,next;
}e[maxm];

void add(int u, int v, int w){
	// 链式前向星，头部插入法
	e[++e_id] = {__填空(1)__};
	h[u] = __填空(2)__;
};

queue <int> q;

bool inque[maxn];
int dis[maxn];
bool vis[maxn];

void spfa(){
	memset(dis,0x3f,sizeof dis);
	dis[s] = 0;
	inque[s] = true;
	q.push(s);
	vis[s] = true;

	while(q.size()){
		int u = q.front();
		q.pop();
		inque[u] = false;
		for(int i=__填空(3)__; __填空(4)__; i=__填空(5)__){
			int v = e[i].v;
			vis[v] = true;
			if(__填空(6)__){ // 松弛操作
				dis[v]=__填空(7)__;
				if(__填空(8)__){ // 避免重复把一个点放入队列
					inque[v] = true;
					q.push(v);
				}
			}
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	int u,v,w;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
        __填空(9)__;
	}

	spfa();

	for(int i=1;i<=n;i++){
		if(vis[i])
			printf("%d ",__填空(10)__);
		else
			printf("%d ",INT_MAX);
	}

	return 0;
}

填空(1) {{ input(1) }}

填空(2) {{ input(2) }}

填空(3) {{ input(3) }}

填空(4) {{ input(4) }}

填空(5) {{ input(5) }}

填空(6) {{ input(6) }}

填空(7) {{ input(7) }}

填空(8) {{ input(8) }}

填空(9) {{ input(9) }}

填空(10) {{ input(10) }}