[C++知识库]NC158 有向无环图的单源最短路径（C++Dijkstra算法）

描述

在一个有向无环图中，已知每条边长，求出1到n的最短路径，返回1到n的最短路径值。如果1无法到n，输出-1

示例1

输入：

5,5,[[1,2,2],[1,4,5],[2,3,3],[3,5,4],[4,5,5]]

返回值：

9

备注：

两个整数n和m,表示图的顶点数和边数。
一个二维数组，一维3个数据，表示顶点到另外一个顶点的边长度是多少
每条边的长度范围[0,1000]。
注意数据中可能有重边

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

struct Edge {
    int u, v, w;
    bool operator<(const Edge& a)const { return w < a.w; }
};


struct cmp {
    template <typename T, typename U>
    bool operator()(T const& left, U const& right) {
        // 以 second 比较。输出结果为 Second 较小的在前; Second 相同时，先进入队列的元素在前。
        if (left.second > right.second)
            return true;
        return false;
    }
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int 顶点数
     * @param m int 边数
     * @param graph intvector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少?
     * @return int
     */
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        // write code here
        vector<vector<int>> g(n + 1, vector<int>(n + 1, INT_MAX));

        for (auto& x : graph) {
            int a = x[0], b = x[1], c = x[2];
            g[a][b] = min(g[a][b], c);  //处理重边
        }

        return dijkstra(g, n, 1, n);
    }

    int dijkstra(vector<vector<int>>& g, int n, int start, int end) {
        //基于bfs的dijkstra算法
        
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq; //优先级队列
        pq.push(make_pair(start, 0));

        vector<int> vis;            //访问过的节点
        map<int, int> parent;       //最短路径中的父节点

        vector<vector<pair<int, int>>> adj(n + 1);      //前驱节点链表生成
        for (int j = 1; j < g.size(); j++) {
            for (int i = 1; i < g[j].size(); i++)
            {
                if (g[j][i] < INT_MAX) 
                    adj[j].push_back(make_pair(i, g[j][i]));
            }
        }

        //初始化distance
        vector<int> distance(n + 1, INT_MAX);
        distance[start] = 0;
        for (auto& x : adj[start]) {
            distance[x.first] = x.second;
        }

        while (!pq.empty()) {
            pair<int, int> tmp = pq.top();
            pq.pop();
            int dist = tmp.second;  //距上个点的距离
            int node = tmp.first;

            vis.push_back(node);

            vector<pair<int, int>> next = adj[node];

            for (auto& x : next) {
                int i = 0;
                for (auto& v : vis) {
                    if (x.first != v) {
                        i++;
                    }
                    if (i == vis.size()) {
                        if ((dist + x.second) <= distance[x.first]) {
                            pq.push(pair<int, int>(x.first, dist + x.second));
                            parent[x.first] = node;
                            distance[x.first] = dist + x.second;
                        }
                    }
                }
            }

        }

        return distance[end];
    }

};

int main() {
    int n = 5, m = 5;
    vector<vector<int>> graph = { {1, 2, 2},{1, 4, 5},{2, 3, 3},{3, 5, 4},{4, 5, 5} };
    Solution st;
    cout << st.findShortestPath(n, m, graph);
    return 0;
}