编辑代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<queue>
#include<vector>
using namespace std;
const int ans = INT_MAX;
const int maxn = 1e6 + 5;
inline int read() {
	register int x = 0; bool flag = 0; char ch = getchar();
	while (ch > '9' or ch < '0') { if (ch == '-')flag = 1; ch = getchar();}
	while (ch >= '0' and ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
	if (flag)return ~(x - 1);
	return x;
}
int n, m, s;
struct edge {
	int to, dis;
	edge(int a, int b) { to = a, dis = b; }
};
vector<edge>e[maxn];
int vis[maxn];
int dis[maxn];
void SPFA() {
	for (register int i = 1; i <= n; i++) {
		vis[i] = 0;
		dis[i] = maxn;
	}
	queue<int>q;
	q.push(s);
	vis[s] = 1;
	dis[s] = 0;
	while (!q.empty()) {
		register int a = q.front();
		q.pop();
		vis[a] = 0;
		for (register int i = 0; i < e[a].size(); i++) {
			if (dis[e[a][i].to] > e[a][i].dis + dis[a]) {
				dis[e[a][i].to] = e[a][i].dis + dis[a];
				if (!vis[e[a][i].to])
					q.push(e[a][i].to);
			}
		}
	}
}
int main() {
	n = read(); m = read(); s = read();
	for (register int i = 1; i <= m; i++) {
		register int a, b,c;
		a = read(); b = read(); c = read();
		e[a].push_back(edge(b, c));
	}
	SPFA();
	for (register int i = 1; i <= n; i++)
		if (dis[i] != maxn)
			cout << dis[i] << " ";
		else
			cout << ans << " ";
	return 0;
}