MediumRating 1680
2492. Minimum Score of a Path Between Two Cities
depth-first-searchbreadth-first-searchunion-findgraph
解題說明
Minimum Score of a Path Between Two Cities
題目描述：
給定 n 個城市和一些帶權無向邊 roads。一條路徑的「分數」定義為路徑上所有邊的最小權重。求從城市 1 到城市 n 的所有路徑中，最小可能分數。注意：路徑可以重複經過節點和邊。
解題思路： 關鍵觀察：由於路徑可以重複經過邊和節點，問題等價於找出城市 1 和城市 n 所在的連通分量中，所有邊的最小權重。
原因：只要一條邊在連通分量中，我們就可以繞路走過它，使得路徑包含這條邊，從而拉低分數。
解法：
- 用 BFS/DFS 或 Union-Find 找出城市 1 所在的連通分量。
- 返回該連通分量中所有邊的最小權重。
C++ 解法
複雜度分析
時間複雜度：O(n + E) — BFS 遍歷所有可達節點和邊，E 為邊數。
空間複雜度：O(n + E) — 鄰接表和訪問陣列。
虛擬碼
1. Build adjacency list with weights 2. BFS from node 1: a. For each visited node u, examine all edges (u, v, w) b. Update minWeight = min(minWeight, w) c. If v not visited, mark visited and enqueue 3. Return minWeight
其他解法
Union-Find 解法 O(E * alpha(n))：用並查集合併所有邊。最後遍歷所有邊，若邊的兩端點與節點 1 在同一連通分量，則用其權重更新最小值。
DFS 解法 O(n + E)：與 BFS 邏輯相同，用 DFS 遍歷連通分量並追蹤最小邊權。
延伸思考
- 如果路徑不允許重複經過邊（簡單路徑），問題難度如何變化？
- 如果要求最大可能分數（路徑中邊的最小值的最大值），如何解決？（提示：最大瓶頸路徑問題）
- 為什麼「可以重複經過邊」使問題變得更簡單？直觀解釋是什麼？