LeetCode 解題筆記：2492. Minimum Score of a Path Between Two Cities

作者：王一哲
日期：2026年7月4日


LeetCode 題目連結：2492. Minimum Score of a Path Between Two Cities

解題想法

中等難度題。題目給一張無向圖兩個節點之間的道路距離，圖中共有 $n$ 個節點，編號為 $1$ 到 $n$，要從節點 $1$ 走到節點 $n$，找出路徑上最知的道路距離。這題可以重覆走到同一個節點上，可以重覆走同一條邊，所以只要用 BFS 找出所有與節點 $1$ 相連的節點，輸出這些道路的最短距離即可。

Python 程式碼

Runtime: 153 ms, beats 71.11%. Memory: 69.20 MB, beats 79.52%.

class Solution:
    def minScore(self, n: int, roads: List[List[int]]) -> int:
        # 用接鄰矩陣存無向圖
        adj = [[] for _ in range(n+1)]
        for u, v, d in roads:
            adj[u].append((v, d))
            adj[v].append((u, d))
        # 用 BFS 找出所有與節點 1 連接的節點
        que = deque([1])
        visited = [False] * (n+1)
        visited[1] = True
        imin = float('inf')
        while que:
            u = que.popleft()
            for v, d in adj[u]:
                imin = min(imin, d)  # 只要相連就更新 imin
                if visited[v]: continue
                visited[v] = True
                que.append(v)
        # End of BFS. 輸出 imin
        return imin

C++ 程式碼

Runtime: 52 ms, beats 79.45%. Memory: 132.84 MB, beats 67.96%.

class Solution {
public:
    int minScore(int n, vector<vector<int>>& roads) {
        // 用接鄰矩陣存無向圖
        vector<vector<pair<int, int>>> adj (n+1);
        for(const auto& road : roads) {
            int u = road[0], v = road[1], d = road[2];
            adj[u].push_back({v, d});
            adj[v].push_back({u, d});
        }
        // 用 BFS 找出與節點 1 相連的節點
        queue<int> que;
        que.push(1);
        vector<bool> visited (n+1, false);
        visited[1] = true;
        int imin = INT_MAX;
        while(!que.empty()) {
            int u = que.front();
            que.pop();
            for(const auto& [v, d] : adj[u]) {
                imin = min(imin, d);  // 只要相連就更新 imin
                if (visited[v]) continue;
                visited[v] = true;
                que.push(v);
            }
        }
        return imin;
    }
};