设计可以求最短路径的图类

类包括根据顶点数和边初始化的构造函数，添加边，求两点最短路径等函数

1. 邻接矩阵

class Graph {
private:
    vector<vector<int>> graph;
public:
    Graph(int n, vector<vector<int>>& edges) {
        graph.resize(n,vector<int>(n,INT_MAX/2));
        for(auto&edge:edges){
            int from = edge[0];
            int to = edge[1];
            graph[from][to] = edge[2];
        }
    }
    
    void addEdge(vector<int> edge) {
        int from = edge[0];
        int to = edge[1];
        graph[from][to] = edge[2];
    }
    
    int shortestPath(int node1, int node2) {
        int n = graph.size();
        vector<bool> vis(n);
        vector<int> dis(n,INT_MAX/2);
        dis[node1] = 0;
        for(int times=0;times<n;times++){//最多遍历n次
            int cur = -1;
            for(int i=0;i<n;i++){//贪心找最小值
                if(vis[i]||dis[i]==INT_MAX/2) continue;//跳过已经选取的点和无法到达的点
                if(cur==-1||dis[i]<dis[cur]) cur = i;
            }
            if(cur==-1) return -1;//表示无法到达目标
            if(cur==node2) break; //找到目标直接跳出，此时dis[cur]即为最短路径，无需再更新
            vis[cur] = 1;
            //找到当前最近点后，根据最近点进行更新
            for(int i=0;i<n;i++){
                if(vis[i]||graph[cur][i]==INT_MAX/2) continue;//对应点已选取，或对应的边不存在，无需更新
                dis[i] = min(dis[i],dis[cur]+graph[cur][i]);
            }
        }
        return dis[node2]==INT_MAX/2?-1:dis[node2];
    }
};