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 } -- https://i.imgur.com/r9FBAGO.gif -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.129.148 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722007576.A.C77.html