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
}