堆优化Dijkstra

#include <bits/stdc++.h>
#define MAXN 100005
#define _INT_MAX_ 1000000000
using namespace std;
int dis[MAXN]; // dijkstra
vector<int> G[MAXN], val[MAXN]; // 邻接表
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m, s;
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		G[u].push_back(v);
		val[u].push_back(w);
	}
	for (int i = 1; i <= n; i++) {
		dis[i] = _INT_MAX_;
	}
	priority_queue<int> q; // 堆优化
	q.push(s);
	dis[s] = 0;
	while(!q.empty()){
		int x = q.top(); q.pop();
		for (int i = 0; i < G[x].size(); i++) {
			dis[G[x][i]] = min(dis[G[x][i]], dis[x] + val[x][i]);
			q.push(G[x][i]);
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << dis[i] << ' ';
	}
	cout << endl;
	return 0;
}

MLE on #3，其他的基本上都是 1.20s