Dijkstra算法 - 单个节点到所有节点的最短路

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
 
vector<pi> G[100005];
int n, m, s;
int dist[100005];
 
int main()
{
    cin >> n >> m >> s;
    s--;    // change to 0-base
    for(int i=0; i < m; i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        a--, b--;
        G[a].push_back({b,c});
    }
    priority_queue<pi, vector<pi>, greater<pi>> q;
    q.push({0,s});
    fill(dist, dist+n, 1e9);
    dist[s] = 0;
    while (!q.empty()) {
        int u = q.top().second, du = q.top().first;
        q.pop();
        if (du != dist[u]) continue;
        for (auto p: G[u]) {
            int v = p.first, dv = p.second;
            if (dist[u] + dv < dist[v]) {
                dist[v] = dist[u] + dv;
                q.push({dist[v], v});
            }
        }
    }
    for(i=0; i < n; i++)
        cout << dist[i] == 1e9 ? -1 : dist[i] << ' ';
    return 0;
}