1334. Find the City With the Smallest Number of Neighbors at a Threshold
Distance
有n个城市，0~n-1
edges[i]=[from_i,to_,weight_i]
并且给一个distanceThreshold
请回传一个城市
以该城市当起点能在distanceThershold到达其他城市的数目最少
如果有多个城市符合条件，则回传编号最大的
思路：
就对每个城市去寻找到其他城市的最小路径
看在distanceThreshold有几个
最后在比较哪个城市能到达的城市最少
就可以得到答案了
golang code :
func findTheCity(n int, edges [][]int, distanceThreshold int) int {
paths, reachable := make([][]int, n), make([][]int, n)
res := 0
for i := 0; i < n; i++ {
paths[i] = make([]int, n)
for j := 0; j < n; j++ {
paths[i][j] = math.MaxInt32
}
}
for _, val := range edges {
paths[val[0]][val[1]] = val[2]
paths[val[1]][val[0]] = val[2]
paths[val[0]][val[0]] = 0
paths[val[1]][val[1]] = 0
}
for i := 0; i < n; i++ {
mincity := -1
mindis := math.MaxInt32
rec := make([]bool, n)
for {
for j := 0; j < n; j++ {
if paths[i][j] < mindis && !rec[j] {
mincity = j
mindis = paths[i][j]
}
}
if mincity == -1 || mindis > distanceThreshold {
break
}
for j := 0; j < n; j++ {
if paths[i][j] > paths[i][mincity]+paths[mincity][j] {
paths[i][j] = paths[i][mincity] + paths[mincity][j]
}
}
mindis = math.MaxInt32
rec[mincity] = true
reachable[i] = append(reachable[i], mincity)
}
}
for i := 0; i < n; i++ {
if len(reachable[i]) <= len(reachable[res]) {
res = i
}
}
return res
}