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;
}
}