参加科学大会-卡玛（堆优化版Dijkstra）

学习参考： 代码随想录
与 Prim 类似，当节点数目较多，边的数量很小的时候（稀疏图），可以考虑从边的角度来求最短路，邻接矩阵遇到稀疏图，会导致申请过大的二维数组造成空间浪费 且遍历 边 的时候需要遍历整个n * n矩阵，造成时间浪费。这时使用邻接链表明显更加符合需求。
而在朴素版Dijkstra中，需要一个for循环来遍历节点，并找出未访问节点，然后对每个为访问节点更新minDist数组，即源点到为访问节点的最小权重。
如果采取小顶堆来存放边，并按照边权重的大小进行排序，那么我们每次从堆中取出的边便是权重最小的边，那么就无须花费两层for循环来寻找最近的节点了。

思路依然是 dijkstra 三部曲：

• 第一步，选源点到哪个节点近且该节点未被访问过
• 第二步，该最近节点被标记访问过
• 第三步，更新非访问节点到源点的距离（即更新minDist数组）

堆优化的时间复杂度 只和边的数量有关 和节点数无关，在 优先级队列中 放的也是边

#include <bits/stdc++.h>
using namespace std;

struct cmp{
    bool operator()(const pair<int, int>& p1, const pair<int, int>& p2){
        return p1.second > p2.second;
    }
};

int main(){
    int n, m, s, e, v;
    cin >> n >> m;
    vector<list<pair<int, int>>> graph(n + 1);
    while(m--){
        cin >> s >> e >> v;
        graph[s].push_back(make_pair(e, v));
    }
    vector<int> minDist(n + 1, INT_MAX);
    vector<bool> visited(n + 1, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pque;
    int start = 1, end = n;
    pque.push(make_pair(start, 0));
    
    while(!pque.empty()){
        auto [cur, val] = pque.top();
        pque.pop();
        
        if(visited[cur]){
            continue;
        }
        
        visited[cur] = true;
        minDist[cur] = val;
        
        for(auto& edge : graph[cur]){
            if(!visited[edge.first] && edge.second + minDist[cur] < minDist[edge.first]){
                minDist[edge.first] = edge.second + minDist[cur];
                pque.push(make_pair(edge.first, minDist[edge.first]));
            }
        }
    }
    
    if(minDist[end] == INT_MAX){
        cout << -1 << endl;
    }else{
        cout << minDist[end] << endl;
    }
    return 0;
}