dijkstra 版本

#include <bits/stdc++.h>

using namespace std;

int n, m, s;

struct Edge {
    int u, v, w;
};

vector<Edge> adj[10010];
int dis[10010];
int vis[10010];

struct Node {
    int v, d;

    bool operator<(const Node &t) const {
        return d > t.d;
    }
};


void dijkstra(int s) {
    for (int i = 1; i <= n; ++i) {
        dis[i] = INT_MAX;
        vis[i] = 0;
    }

    priority_queue<Node> pq;
    pq.push({s, 0});
    dis[s] = 0;

    while (!pq.empty()) {
        Node t = pq.top();
        pq.pop();
        if (vis[t.v]) {
            continue;
        }
        vis[t.v] = 1;
        for(int i = 0;i < adj[t.v].size(); ++i){
            Edge e = adj[t.v][i];
            if (dis[e.v] > dis[e.u] + e.w) {
                dis[e.v] = dis[e.u] + e.w;
                pq.push({e.v, dis[e.v]});
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m >> s;

    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({u, v, w});
    }
    dijkstra(s);

    for (int i = 1; i <= n; ++i) {
        cout << dis[i] << " ";
    }

    return 0;
}