最短路径算法-Dijkstra

Dijkstra模板（优先队列优化）

struct Dijkstra {
    using pii=pair<int,int>;
    vector<vector<pii>> g;
    vector<int> dis;
    vector<bool> vis;
    int n;

    Dijkstra(int n) : n(n),g(n + 2),dis(n + 2, INF),vis(n + 2, false) {}
    
    void addEdge(int u, int v, int w) {
        g[u].push_back({v, w});//v:目标点 w:边权
    }
    void run(int s) {
        priority_queue<pii,vector<pii>,greater<pii>> pq;
        dis[s] = 0;
        pq.push({0,s});//先存距离再存点，原因是pair默认是按照first排序的
        while(!pq.empty()){
            int d=pq.top().first,u=pq.top().second;
            pq.pop();
            if(vis[u]) continue;//因为同一个点可能会多次入队，但是先出来的一定是距离最小的合法情况。对于剩下没出来的点，直接pop即可。
            vis[u]=true;//以u为中心计算
            for(auto &node:g[u]){
                int v=node.first,w=node.second;
                if(dis[u]+w<dis[v]){
                    dis[v]=dis[u]+w;
                    pq.push({dis[v],v});
                }
            }
        }
    }
    void printDistances() {
        for (int i = 1; i <= n; ++i) {
            cout << dis[i] << " ";
        }
        cout << endl;
    }
};