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

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 1, maxm = 5e5 + 1;
int n, m, s;
struct edge{
	int fr, to, wt, nxt;
}e[maxm];
int cnt_edge = 0, head[maxn] = {};
queue <int>q;
int dis[maxn] = {};
bool vis[maxn] = {};

void add_edge(int u, int v, int w){
	e[++cnt_edge] = (edge){u, v, w, head[u]};
	head[u] = cnt_edge;
}

void spfa(){
	memset(dis, 0x3f, (n + 1) * sizeof(int));
	dis[s] = 0;
	q.push(s);
	while(q.size()){
		int u = q.front();
		q.pop();
		vis[u] = false; 
		for(int i = head[u]; i != -1; i = e[i].nxt){
			int v = e[i].to;
			if(dis[v] > dis[u] + e[i].wt){
				dis[v] = dis[u] + e[i].wt;
				if(!vis[v]){
					q.push(v);
					vis[v] = true;//  
				}
			}
		}
	}
}
int main(){
	cin >> n >> m >> s;
	for(int i = 1; i <= n; ++i) head[i] = -1;
	
	for(int i = 1; i <+ m; ++i){
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		add_edge(u,v,w);
	}
	
	spfa();
	
	for(int i = 1; i <= n; ++i) {
		if(dis[i] == 0x3f3f3f3f)
			printf("%d ", 0x7fffffff);
		else
			printf("%d ", *(dis + i));
		
	}
	return 0;
}