题解 | 单源最短路

#include <queue>
#include <utility>
class Solution {
  public:
    /*
        从起点开始，不断选择 当前距离最短且未访问 的节点，把它的邻居的距离更新成更短的值，直到所有节点都确定了最短距离。
        创建邻接表->创建最短距离表、是否遍历过表->创建小根堆->初始化小根堆->循环:提取对顶,更新边能到的节点离起点的最近距离;直到堆为空;
     */

    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        //邻接表：行号表示起点，pair就是到节点和距离；
        vector< vector< pair<int, int>>> adj(n + 1);
        //初始化邻接表
        for (auto g : graph) {
            int i = g[0]; //起点
            int v = g[1]; //终点
            int w = g[2]; //距离
            adj[i].push_back(make_pair(v, w));  //加入邻接表
        }

        //D杰斯特算法：从起点开始，遍历每个边，更新边能到达的节点的最短距离，对更新了的节点遍历，遍历过了就不用遍历了；
        const int INF = 1e9;
        vector<int> dist(n + 1, INF); //表示从1到i的最短距离，还没有确认最短
        vector<bool> vis(n + 1,
                         false); //vis[i]表示已经遍历过了此节点为起点的边

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>>
                pq;  //小根堆，存放0到u的目前为止的最短距离，用来遍历节点的下一个边

        dist[1] = 0;
        pq.push({0, 1});

        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();  //对这个节点，遍历下边

            if (vis[u]) {
                continue;
            } else {
                vis[u] = true;
            }

            for (auto& edge : adj[u]) { //对以u开头的边遍历，更新
                int w = edge.second;  //距离
                int v = edge.first; //下一个节点

                if (dist[v] > w + d) {
                    dist[v] = d + w; //更新0到v的最短距离
                    pq.push({dist[v], v});  //对到v的最短距离
                }
            }
        }

        // 初始化
        return dist[n] == INF ? -1 : dist[n];
    }
};