Find the City With the Smallest Number of Neighbors at a Threshold Distance
给一个图, 点是city, 边是neighborhood 和一个int, int代表一个最大边的权重和, 问在这个int下, city能到所有city中, 最少的那个的index. 如果有相同的, 返回靠后的. 这个题要求所有点之间的最短路径, 首推弗洛伊德. 事实证明, 比dij要快, 然后判断下int即可.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
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; } } |