题解 | #演唱会#

#include <bits/stdc++.h>


using namespace std;

// 抽象从节点 0，到其他所有节点的最短路径！

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> edges(n + 1, vector<pair<int, int>>());

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        edges[0].emplace_back(i, x);
    }

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[u].emplace_back(v, w);
        edges[v].emplace_back(u, w);
    }

    vector<long long> d(n + 1, 0x3f3f3f3f);
    queue<int> q;

    // 求最短路径，Bellman-ford 算法
    d[0] = 0;
    q.push(0);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto [nx, w] : edges[u]) {
            if (d[nx] > d[u] + w) {
                d[nx] = d[u] + w;
                q.push(nx);
            }
        }
    }

    for (int i = 1; i <= n; i++) cout << d[i] << " ";

    return 0;
}