P3371 【模板】单源最短路径（弱化版）

#include <bits/stdc++.h>
using namespace std;
const int N = 2000010;
int n, m, hand[N], tot, x, y, v, s;
long long dis[N];
bool ff[N];
typedef pair <int, int> pii;
priority_queue <pii, vector< pii >, greater < pii > >q;
struct liu {
	int  w, to, next;
} e[N];
void add(int x, int y, int v) {
	e[++tot].next = hand[x];
	e[tot].to = y;
	e[tot].w = v;
	hand[x] = tot;
}
void dijk(int s) {
	memset(dis, 0x3f, sizeof dis);
	dis[s] = 0;
	q.push({0, s});
	while (!q.empty()) {
		auto t = q.top();
		q.pop();
		int x = t.first, y = t.second;
		if (ff[y])continue;
		ff[y] = true;
		for (int i = hand[y]; i; i = e[i].next) {
			if (dis[e[i].to] > dis[y] + e[i].w) {
				dis[e[i].to] = dis[y] + e[i].w;
				q.push({dis[e[i].to], e[i].to});
			}
		}
	}
}
int main() {
	cin >> n >> m >> s;
	for (int i = 1; i <= m ; i++) {
		cin >> x >> y >> v;
		add(x, y, v);
	}
	dijk(s);
	for (int i = 1; i <= n; i++) {
		if (dis[i] != 0x3f)cout << dis[i] << " ";
		else cout << 2147483647 << " ";
	}
	return 0;
}