济南建设工程有限公司_温州企业自助建站系统_百度竞价排名又叫什么_百度竞价推广流程

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

题目

题目解析及思路

题目要求对于每一组询问都返回node1到node2的最小距离

用floyd将每对顶点的距离都求出来，当addedge时再更新所有可能被更新的距离

代码

class Graph {//邻接表vector<vector<int>> f;const int INF = INT_MAX / 3;
public:Graph(int n, vector<vector<int>>& edges) {f.resize(n,vector<int>(n,INF));//自己到自己是0for(int i=0;i<n;i++){f[i][i] = 0;}for(auto e : edges){f[e[0]][e[1]] = e[2];}//floydfor(int k=0;k<n;k++){for(int i=0;i<n;i++){for(int j=0;j<n;j++){f[i][j] = min(f[i][j],f[i][k] + f[k][j]);}}}}void addEdge(vector<int> e) {int x = e[0],y = e[1],w = e[2],n = f.size();//说明不可能更新if(w >= f[x][y]){return;}//在x，y之间连边，任意i到j就多了一条路径:i->x->y->jfor(int i=0;i<n;i++){for(int j=0;j<n;j++){f[i][j] = min(f[i][j],f[i][x] + w + f[y][j]);}}}int shortestPath(int node1, int node2) {int ans = f[node1][node2];return ans < INF ? ans : -1;}
};