题解 | #单源最短路#

class Solution {
public:
    const int inf = 0x3f3f3f3f;
    struct Node{
        int v;
        int dis;
        Node(int _v, int _dis):v(_v), dis(_dis){}
        bool operator < (const Node& other) const{
            return dis > other.dis;
        }
    };
    int graphs[505][505];
    vector<bool> vis;
    vector<int> dist;
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        // write code here
        memset(graphs, inf, sizeof(graphs));
        dist.resize(n + 1, inf);
        vis.resize(n + 1, false);
        for(int i = 0; i < m; i ++){
            int u = graph[i][0], v = graph[i][1], dis = graph[i][2];
            graphs[u][v] = min(graphs[u][v], dis); //有向边
        }
        priority_queue<Node> pq;
        pq.push({1, 0});
        dist[1] = 0;
        int cnt = 0;
        while(!pq.empty()){
            Node node = pq.top(); pq.pop();
            int u = node.v, dis = node.dis;
            if(!vis[u]){
                vis[u] = true;
                cnt ++;
                if(cnt == n) break;
            }else continue;
            for(int v = 1; v <= n; v ++){
                if(v == u || graphs[u][v] == inf) continue;
                if(dist[u] + graphs[u][v] < dist[v]){
                    dist[v] = dist[u] + graphs[u][v];
                    pq.push({v, dist[v]});
                }
            }
        }
        return dist[n] >= inf ? -1 : dist[n];
    }
};