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

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

题目链接：2642. 设计可以求最短路径的图类

代码如下：

class Graph 
{
public:
    Graph(int n, vector<vector<int>>& edges) 
    {
        this->n=n;
        this->graph=vector<vector<int>>(n,vector<int>(n,max));
        for(const auto& edge:edges)
        {
            int x=edge[0];
            int y=edge[1];
            int cost=edge[2];
            graph[x][y]=cost;
        }
    }
    
    void addEdge(vector<int> edge) 
    {
        graph[edge[0]][edge[1]]=edge[2];
    }
    
    //迪杰斯特拉
    int shortestPath(int node1, int node2) 
    {
        vector<bool> visited(n,false);
        vector<int> dist(n,max);
        dist[node1]=0;
        for(int i=0;i<n;i++)
        {
            int t=-1;
            for(int j=0;j<n;j++)
            {
                if(!visited[j]&&(t==-1||dist[t]>dist[j]))
                    t=j;
            }
            visited[t]=true;
            for(int j=0;j<n;j++)
                dist[j]=min(dist[j],dist[t]+graph[t][j]);
        }
        return dist[node2]>=max?-1:dist[node2];
    }
private:
    vector<vector<int>> graph;
    int n;
    const int max=1<<29;
};

/**
 * 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);
 */