#include <iostream>
#include <algorithm>
#include <climits>
#include <cmath>
#include <queue>
using namespace std;
const int inf = 1e9 + 100;
const int maxn = 2e5 + 10;
struct node{
int v;
int len, nex;
}edge[maxn << 1];
struct value{
int id;
int val;
value(int _id = 0, int _val = 0) {
id = _id, val = _val;
}
};
int head[maxn];
bool vis[maxn];
int d[maxn];
int cnt;
int n, m, s;
void add_edge(int u, int v, int val) {
edge[++cnt].v = v;
edge[cnt].nex = head[u];
edge[cnt].len = val;
head[u] = cnt;
}
bool operator < (value x, value y) {
return x.val > y.val;
}
void Dijkstra() {
fill(d, d + maxn, inf);
d[s] = 0;
priority_queue<value>que;
que.push(value(s, 0));
while(!que.empty()) {
value cur = que.top();
que.pop();
if(vis[cur.id] == true) continue;
vis[cur.id] = true;
int id = cur.id;
for(int i = head[id]; i; i = edge[i].nex) {
int v = edge[i].v;
if(d[v] > d[id] + edge[i].len) {
d[v] = d[id] + edge[i].len;
que.push(value(v, d[v]));
}
}
}
}
int main() {
int u, v, w;
cin >> n >> m >> s;
for(int i = 1; i <= m; i++) {
cin >> u >> v >> w;
add_edge(u, v, w);
}
Dijkstra();
for(int i = 1; i <= n; i++) {
cout << d[i] << " ";
}
return 0;
}
Processed:
0.020, SQL:
8
