单源最短路径算法

https://leetcode.cn/problems/design-graph-with-shortest-path-calculator/

Dijkstra 算法介绍

https://leetcode.cn/problems/network-delay-time/solutions/2668220/liang-chong-dijkstra-xie-fa-fu-ti-dan-py-ooe8/

邻接矩阵建图 + 朴素 Dijkstra

class Graph {
public:
    vector<vector<int>>g;
    Graph(int n, vector<vector<int>>& edges) {
        g.resize(n,vector<int>(n,INT_MAX/2));
        for(auto &e:edges){
            g[e[0]][e[1]]=e[2];
        }
    }
    
    void addEdge(vector<int> e) {
        g[e[0]][e[1]]=e[2];
    }
    
    int shortestPath(int st, int ed) {
        int n=g.size();
        vector<int>dis(n,INT_MAX/2),vis(n);
        dis[st]=0;
        while(true){
            int x=-1;
            for(int i=0;i<n;i++){
                if(!vis[i]&&(x<0||dis[i]<dis[x])){
                    x=i;
                }
            }
            if(x<0||dis[x]==INT_MAX/2){
                return -1;
            }
            if(x==ed){
                return dis[x];
            }
            vis[x]=true;
            for(int y=0;y<n;y++){
                dis[y]=min(dis[y],dis[x]+g[x][y]);
            }
        }
    }
};

/**
 * Your Graph object will be instantiated and called as such:
 * Graph* obj = new Graph(n, edges);
 * obj->addEdge(edge);
 * int param_2 = obj->shortestPath(node1,node2);
 */