Find the City With the Smallest Number of Neighbors at a Threshold Distance

给一个图, 点是city, 边是neighborhood 和一个int, int代表一个最大边的权重和, 问在这个int下, city能到所有city中, 最少的那个的index. 如果有相同的, 返回靠后的. 这个题要求所有点之间的最短路径, 首推弗洛伊德. 事实证明, 比dij要快, 然后判断下int即可.

class Solution {
     public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] d = new int[n][n];
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
               d[i][j] = Integer.MAX_VALUE / 2; // max
            }
        }
        for(int[] edge : edges) {
            d[edge[0]][edge[1]] = edge[2];
            d[edge[1]][edge[0]] = edge[2];
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (j == k) { // opt
                        continue;
                    }
                    if (d[j][k] > d[j][i] + d[i][k]) {
                        d[j][k] = d[j][i] + d[i][k];
                    }
                }
            }
        }
        int min = Integer.MAX_VALUE;
        int min_index = -1;
        for(int i = 0; i < n; i++) {
            int count  = 0 ;
            for (int j = 0; j < n; j++) {
                if (d[i][j] == Integer.MAX_VALUE / 2 || d[i][j] > distanceThreshold)
                    continue;
                count++;
            }
            if (count <= min){
                min = count;
                min_index = i;
            }
        }
        return min_index;
    }
}