P4779 【模板】单源最短路径（标准版）

// Heap Dijkstra o(mlogm) 
#include <bits/stdc++.h>
using namespace std;
const int N=100005, INF=0X3F3F3F3F; 
int d[N]; 
bool vis[N]; 
int n, m, s;
struct node {int v, w;friend bool operator < (node a, node b) {return a.w > b.w; // 小根堆、符号反着写 }
};
vector<node> e[N];void dijkstra(int s) {memset(d, INF, sizeof d); d[s]=0; priority_queue<node> q;q.push({s, 0});while(!q.empty()) {int u=q.top().v; q.pop();if(vis[u]) continue; //第1次出队才扩展，再出队跳过vis[u]=true;for(auto i : e[u]) {int v=i.v, w=i.w;if(d[v] > d[u]+w) {d[v]=d[u]+w;q.push({v, d[v]});}}}
}int main() {cin >> n >> m >> s;for (int i=1, u, v, w; i <= m; i++) {cin >> u >> v >> w;e[u].push_back({v, w});}dijkstra(s);for (int i=1; i <= n; i++) cout << d[i] << " ";return 0;
}