MediumRating 1855
1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
dynamic-programminggraphshortest-path
解題說明
Find the City With the Smallest Number of Neighbors at a Threshold Distance
題目描述： 有 n 個城市，編號從 0 到 n-1，以及一些加權無向邊。給定一個距離閾值 distanceThreshold，找出在閾值距離內可到達的鄰居城市最少的城市。如果有多個城市的鄰居數相同，回傳編號最大的城市。
解題思路： 使用 Floyd-Warshall 演算法計算所有城市之間的最短路徑。然後對每個城市統計在閾值距離內可到達的其他城市數量，找出數量最少的城市。Floyd-Warshall 適合此題，因為需要全源最短路徑（all-pairs shortest paths），且 n 最大只有 100。
C++ 解法
複雜度分析
時間複雜度：O(n³) — Floyd-Warshall 演算法的標準時間複雜度
空間複雜度：O(n²) — 儲存所有城市對之間的最短距離矩陣
虛擬碼
1. Initialize distance matrix dist[n][n] with infinity, dist[i][i] = 0 2. For each edge (u, v, w), set dist[u][v] = dist[v][u] = w 3. Floyd-Warshall: for each intermediate vertex k, for each pair (i, j), relax dist[i][j] through k 4. For each city i, count neighbors j where dist[i][j] <= distanceThreshold 5. Return the city with minimum count (largest index if tie)
其他解法
方法二：Dijkstra（每個節點執行一次） 對每個城市執行一次 Dijkstra 演算法，時間複雜度 O(n × (m log n))。當邊數 m 遠小於 n² 時效率更好。
方法三：Bellman-Ford 對每個城市執行 Bellman-Ford，時間複雜度 O(n² × m)。通常比 Floyd-Warshall 慢，但可以處理負權邊（雖然此題不需要）。
延伸思考
- 如果城市數量很大（n > 10000）但邊很稀疏，應該選擇哪種最短路徑演算法？
- 如果圖是有向的，解法需要如何修改？
- 如果需要動態新增或刪除邊，如何有效地更新結果？