编辑代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<climits>
using namespace std;
#define ll long long 
#define INF INT_MAX
const int maxn = 1e6;
inline ll read() {
	ll x = 0; bool flag = 0; char ch = getchar();
	while (ch < '0' || ch>'9') { if (ch == '-')flag = 1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
	if (flag)
		return ~(x - 1);
	return x;
}
inline void print(ll x) {
	if (x > 9) print(x / 10);
	if (x < 0) { x = ~(x - 1); putchar('-'); };
	putchar(x % 10 + '0');
}
struct edge {
	int from, to, dis;
}cj;
vector<edge> e[maxn];
ll n, m, s;
struct node {
	int w, dis;
	bool operator <(const node& x)const {
		return dis > x.dis;
	}
}start;
bool visit[maxn];
ll dis[maxn];
void dij() {
	priority_queue<node >q;
	for (int i = 1; i <= n; i++)
		dis[i] = INF;
	start.w = s;
	start.dis = 0;
	dis[s] = 0;
	q.push(start);
	while (!q.empty()) {
		node e0;
		e0 = q.top();
		q.pop();
		int u = e0.w;
		if (visit[u])
			continue;
		visit[u] = 1;
		for (int i = 0; i < e[u].size(); i++) {
			int v = e[u][i].to;
			if (dis[u] + e[u][i].dis < dis[v]) {
				dis[v] = dis[u] + e[u][i].dis;
				e0.w = v;
				e0.dis = dis[v];
				q.push(e0);
			}
		}
	}
}
int main() {
	n = read(); m = read(); s = read();
	for (int i = 1; i <= m; i++) {
		cj.from = read();
		cj.to = read();
		cj.dis = read();
		e[cj.from].push_back(cj);
	}
	dij();
	for (int i = 1; i <= n; i++) {
		cout << dis[i] << " ";
	}
}