#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];

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

    queue<int> pq;
    pq.push(s);
    dis[s] = 0;
    vis[s] = 1;

    while (!pq.empty()) {
        int t = pq.front();
        pq.pop();
        vis[t] = 0;

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


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});
    }
    SPFA(s);

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

    return 0;
}

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;
}

暴力版本

#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];

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

    dis[s] = 0;

    while(1){
        int u = 0;
        for( int i = 1;i <= n; ++i){
            if(!vis[i] && (u == 0 || dis[i] < dis[u])){
                u = i;
            }
        }
        if(u == 0){
            break;
        }
        vis[u] = 1;
        for(int  i = 0;i < adj[u].size(); ++i){
            int v = adj[u][i].v;
            if(dis[v] > dis[u] + adj[u][i].w){
                dis[v] = dis[u] + adj[u][i].w;
            }
        }
    }
}


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;
}