洛谷P3371 https://www.luogu.com.cn/problem/P3371

#include <iostream>
#include <cstring>
#include <climits>
using namespace std;

const int N = 10010, M = 500010, INF = 0x3f3f3f3f;

int n, m, s;
int h[N], e[M], w[M], ne[M], idx;
int d[N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

// 定义成 int 会TLE, 定义成 void 就AC了
int dijkstra() {
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;

    for (int i = 0; i < n; i++) {
        int t = -1;
        for (int j = 1; j <= n; j++) {
            if (!st[j] && (t == -1 || d[j] < d[t]))
                t = j;
        }

        st[t] = true;
        if (d[t] == INF) continue;
        for (int k = h[t]; k != -1; k = ne[k]) {
            int j = e[k];
            if (!st[j]) {
                d[j] = min(d[j], d[t] + w[k]);
            }
        }
    }
}

int main() {
    memset(h, -1, sizeof(h));
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    dijkstra();

    for (int i = 1; i <= n; i++) 
        if (d[i] != INF) cout << d[i] << ' ';
        else cout << INT_MAX << ' ';

    return 0;
}