$\mathcal{R} . \mathcal{T}$

代码：

#include <bits/stdc++.h>
#define INF 0x7fffffff
typedef long long ll;
using namespace std;

ll n, m, s, minn;
int cnt;
ll head[500010], dis[500010];
bool visit[500010];

template <typename _Ip>
inline void read(_Ip &x) {
    char ch = getchar(), sgn = 0; x = 0;
    while (ch ^ '-' && !isdigit(ch)) ch = getchar();
    if (ch == '-') ch = getchar(), sgn = 1;
    while (isdigit(ch)) x = (x<<3)+(x<<1) + (ch^48), ch = getchar();
    if (sgn) x = -x;
}

template <typename _Op>
inline void write(_Op x) {
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
// -------- 日常快读快写请忽略 --------

struct Edge {
	int to;
	int next;
	int w;
} edge[100010];

void add(int u, int v, int w) {
	edge[++cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt;
}

int main() {
	read(n);read(m);read(s);
	for (int i = 1; i <= n; ++i) {
		dis[i] = INF;
	}
	int u, v, w;
	for (int i = 0; i < m; ++i) {
		read(u);read(v);read(w);
		add(u, v, w);
	}
	dis[s] = 0;
	ll pos = s;
	while(visit[pos] == false) {
		visit[pos] = true;
		for (int i = head[pos]; i != 0; i = edge[i].next) {
			if (!visit[edge[i].to] && dis[pos]+edge[i].w < dis[edge[i].to]) {
				dis[edge[i].to] = dis[pos] + edge[i].w;
			}
		}
		minn = INF;
		for (int i = 1; i <= n; ++i) {
			if (!visit[i] && minn > dis[i]) {
				minn = dis[i];
				pos = i;
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		write(dis[i]);
		putchar(' ');
	}
	return 0;
}

（抱歉，由于测试用例过长，粘贴到云剪贴板时会直接卡死，所以无法提供样例）