最短路：leetcode1334. 阈值距离内邻居最少的城市

1334. 阈值距离内邻居最少的城市

有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。

返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。

注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。

使用floyd求出每个顶点到其他顶点的最短路。然后根据题目意思遍历即可。

【最短路径问题笔记】Floyd算法求多源最短路径问题_解决所有点对最短路径问题(多源最短路径问题)的floyd算法的空间复杂度为____。-CSDN博客

class Solution {
public:
    int findTheCity(int n, vectorint>>& edges, int distanceThreshold) {
       vectorint>>w(n,vector<int>(n,INT_MAX/2));
       for(auto &e:edges){
           int x = e[0],y=e[1],wt=e[2];
           w[x][y]=w[y][x]=wt;
       }      
       auto f=move(w);
       for(int k = 0;k
           for(int i = 0;i < n;i++){
               for(int j = 0;j
                   f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
               }
           }
       }
       int ans=0;
       int min_cnt=n;
       for(int i=0;i
           int cnt=0;
           for(int j=0;j
               if(j!=i&&f[i][j]<=distanceThreshold){
                   cnt++;
               }
           }
           if(cnt<=min_cnt){
               min_cnt=cnt;
               ans=i;
           }
       }
       return ans;
    }
};