堆优化，dijkstra题解（含注释）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+7;
const int INF=1e18;
vector<pair<ll,int>>g[N];
bool vis[N];
ll dist[N];//起点到i的最短路
void dijkstra(int s,int n){
    for(int i=1;i<=n;i++){
        dist[i]=INF;
        vis[i]=false;
    }
    dist[s]=0;
    //pair<ll,int>first代表距离，second代表点
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>>pq;
    pq.push({0,s});
    while(!pq.empty()){
        ll d=pq.top().first;//起点到当前点的距离
        int u=pq.top().second;//当前的点
        pq.pop();//弹出当前点
        if(vis[u])continue;//当前点遍历过->跳过
        vis[u]=true;
        for(auto [v,w]:g[u]){//v first:u->v  边权值
            if(dist[v]>dist[u]+w){//当前起点到v的距离<当前起点到u的距离+我（u->v)
                dist[v]=dist[u]+w;
                pq.push({dist[v],v});
            }
        }
    }
}
int main(){
    int n,m,s;
    cin>>n>>m>>s;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
    }
    dijkstra(s,n);
    for(int i=1;i<=n;i++){
        if(dist[i]==INF)cout<<-1<<' ';
        else cout<<dist[i]<<' ';
    }
    return 0;
}