玄关求调

#include <bits/stdc++.h>
#define MAXN 100001
using namespace std;
struct edge {
    int v, w;
};
vector<edge> g[MAXN];
long long dis[MAXN];
bool vis[MAXN];
struct gragh {
    int x;
    bool operator > (const gragh &b) const {return dis[x] > dis[b.x];}
};
int main() {
    int n, m, s;
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({ v, w });
    }
    for (int i = 0; i < MAXN; i++)
        dis[i] = 100000000000000ll, vis[i] = false;
    dis[s] = 0;
    priority_queue< gragh, vector<gragh>, greater<gragh> >q;
    q.push({s});
    while (!q.empty()) {
        int x = q.top().x;
        q.pop();
        if (vis[x])
            continue;
        vis[x] = true;
        for (edge ed : g[x])
            if (dis[ed.v] > dis[x] + ed.w) {
                dis[ed.v] = dis[x] + ed.w;
                q.push({ed.v});
            }
    }
    for (int i = 1; i <= n; i++)
        printf("%lld ", dis[i]);
    return 0;
}