题解 | 【模板】单源最短路Ⅲ-A ‖ 非负权图：Dijkstra

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

int main() {
    int n,m,s;
    const long long INF = 1e18;
    while (cin >> n >> m >> s) { // 注意 while 处理多个 case
        vector<long long> ans(n+2,INF);
        vector<vector<pair<int,int>>> bian(n+2);

        priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<>> q;
        
        int a,b,v;
        for (int ii=0;ii<m;ii++) {
            cin >> a >> b >> v;
            bian[a].push_back({b,v});
        }

        q.push({0,s});
        ans[s]=0;

        while(!q.empty()) {
            auto [aa,bb] = q.top();
            q.pop();
            if (aa<=ans[bb]) {
                for (auto& [cc,dd] : bian[bb]) {
                    if (ans[cc]-dd > aa) {
                        ans[cc] = aa + dd;
                        q.push({ans[cc],cc});
                    }
                }
            }
        }

        for (int ii=1;ii<n;ii++)
            cout << (ans[ii]==INF ? -1 : ans[ii]) << " ";
        cout << (ans[n]==INF ? -1 : ans[n]) << endl;
    }
}
// 64 位输出请用 printf("%lld")