LeetCode-1334

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

思路

Flyod 求所有点对之间的最短路，然后 $O(n^2)$ 暴力求解每个点的情况，与全局的 minCount对比并更新结果即可。

AC code

const int inf = 0x3f3f3f3f;

class Solution {
public:
    vector<vector<int>> dp;
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        dp.resize(n, vector<int>(n, inf));
        for(int i = 0; i < n; i++) dp[i][i] = 0;
        for(auto e : edges){
            int a = e[0], b = e[1], c = e[2];
            dp[a][b] = dp[b][a] = c;
        }
        for(int k = 0; k < n; k++){
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
        int idx, mincnt = inf;
        for(int i = 0; i < n; i++){
            int cnt = 0;
            for(int j = 0; j < n; j++){
                if(i != j && dp[i][j] <= distanceThreshold){
                    cnt++;
                }
            }
            if(cnt <= mincnt){
                mincnt = cnt;
                idx = i;
            }
        }
        return idx;
    }
};