题解 | #【模板】单源最短路Ⅲ ‖ 非负权图#

一样的代码，改一下大小和输入权值就行

#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <numeric>
#include <ctime>
#include <string>
#include <bitset>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;

const ll N = 5e5 + 5, mod = 1e9 + 7, inf = 2e18;
const double esp = 1e-8;

int n, m, s;

struct Node {
    ll v, w;
};

vector<Node>g[N];
bool vis[N];
ll dis[N];

struct node {
    ll id, vlu;
    bool operator<(const node& u)const {
        return u.vlu < vlu;
    }
};

void dijk(int s) {
    for (int i = 0; i <= n + 3; i++) {
        dis[i] = inf;
    }

    priority_queue<node>pq;

    pq.push({s, dis[s] = 0});

    while (!pq.empty()) {
        node tem = pq.top();
        pq.pop();

        if (vis[tem.id])continue;
        vis[tem.id] = true;

        for (auto [y, w] : g[tem.id]) {
            if (dis[y] > dis[tem.id] + w) {
                pq.push({y, dis[y] = dis[tem.id] + w});
            }
        }

    }
}

void solve() {
    cin >> n >> m >> s;

    while (m--) {
        ll u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }

    dijk(s);
    for (int i = 1; i <= n; i++) {
        cout << (dis[i] == inf ? -1 : dis[i]) << " \n"[i == n];
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}