题解 | #单源最短路#dijkstra模板题 C++

#include <algorithm>
#include <climits>
#include <vector>
class Solution {
public:
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        int len = graph.size();
        vector<vector<int>> g(n,vector<int>(n,INT_MAX/2));//邻接矩阵，标号从0开始
        for(int i=0;i<m;++i){
            g[graph[i][0]-1][graph[i][1]-1] = min(graph[i][2],g[graph[i][0]-1][graph[i][1]-1]); //去重边
        }
        
        vector<int> dist(n,INT_MAX/2);
        vector<int> vis(n,0);
        dist[0] = 0;//0到自己的距离为0
        for(int i=0;i<n;++i){
            int x = -1;
            for(int y=0;y<n;++y){
                if(!vis[y]&&(x==-1||dist[y]<=dist[x]))
                    x = y;
            }

            vis[x] = 1;
            for(int y=0;y<n;++y){
                dist[y] = min(dist[y], dist[x]+g[x][y]);
            }
        }

        return dist[n-1];
    }
};