LeetCode 解題筆記：3970. Shortest Path With At Most K Consecutive Identical Characters

作者：王一哲
日期：2026年10月30日


LeetCode 題目連結：3970. Shortest Path With At Most K Consecutive Identical Characters

解題想法

中等難度題。題目給一個整數 $n ~(1 \leq n \leq 500000)$，代表有 $n$ 個節點，編號為 $0$ 到 $n-1$。一個二維陣列 $edges$，其中 $edges[i] = [u_i, v_i, w_i]$，代表有一條可以從 $u_i$ 走要 $v_i$ 且權重為 $w_i$ 的邊。再給一個長度為 $n$ 的字串 $labels$，其中 $labels[i]$ 代表節點 $i$ 的標籤。最後給一個整數 $k$，代表路徑上同一個字母最多只能連續出現 $k$ 次。找出所有由節點 $0$ 走到 $n-1$，同一個字母最多能連續出現 $k$ 次的路徑之中，路徑權重加總的最小值。如果沒有這樣的路徑則回傳 $-1$。

首先排除特例，$n$ 等於 $0$，不需要走，回傳 $0$。接下來處理一般狀況。先用接鄰矩陣 $adj$ 存有向圖，記錄從節點 $u$ 可以走到的節點及權重。解題重點在於如何用 Dijkstra 演算法，找走到各節點、各種末端連續相同字母數量對應的最低權重。定義一個大小為 $n \times (k+1)$ 的二維陣列 $dist$，$dist[i][j]$ 代表走到節點 $i$、末端有 $j$ 個連續相同字母對應的最低權重，預設值為超過題目上限的值。用最小優先佇列 $pq$ 儲存待走訪的狀態，內容為 {權重, 節點編號, 字母數量}，權重低的放最上面。寫一個 while 迴圈，若 $pq$ 有資料繼續執行，每次先取出權重 $w$、節點 $u$、字母數量 $cnt$，再檢查 $u$ 可以走到的節點 $v$ 及權重 $d$，如果 $labels[u] == labels[v]$，新的數量 $nxt = cnt + 1$； 反之 $nxt = 1$。如果 $nxt \leq k$ 而且 $w + d < dist[v][nxt]$，找到新的最低權重路徑，更新 $dist[v][nxt]$，將 ${w + d, v, nxt}$ 加入 $pq$。全部跑完之後，答案 $ans$ 為 $dist[n-1][1]$ 到 $dist[n-1][k]$ 之中的最小值。如果 $ans$ 等於預設的極大值，代表找不到路徑，回傳 $-1$。

Python 程式碼

Runtime: 554 ms, beats 13.25%. Memory: 67.95 MB, beats 16.87%.

class Solution:
    def shortestPath(self, n: int, edges: List[List[int]], labels: str, k: int) -> int:
        # 特例，n = 1，不需要走，回傳 0
        if n == 1: return 0
        
        # 一般狀況
        adj = [[] for _ in range(n)]  # u: [(v1, w1), (v2, w2), ...]
        for u, v, w in edges:
            adj[u].append((v, w))
        
        # dist[i][j] 代表走到節點 i、最後一個字母連續出現 j 次的最低權重
        dist = [[float('inf')] * (k + 1) for _ in range(n)]
        dist[0][1] = 0  # 起點，次數1，權重 0

        # Dijkstra 演算法，找符合條件的最低權重路徑
        pq = [(0, 0, 1)]  # 最小優先佇列，(權重，節點編號，最後一個字母連續出現次數)
        while pq:
            w, u, cnt = heapq.heappop(pq)
            # 如果目前 dist 之中的權重較低，跑下一組
            if w > dist[u][cnt]: continue
            
            # 測試 u 可以走到的節點 v
            for v, d in adj[u]:  # u 走到 v，權重 d
                # 相同字母，次數加 1；不同字母，次數重設為 1
                nxt = cnt + 1 if labels[u] == labels[v] else 1
                
                # 次數合法而且走到 v 的路徑權較低
                if nxt <= k and w + d < dist[v][nxt]:                    
                    dist[v][nxt] = w + d
                    heapq.heappush(pq, (w + d, v, nxt))
        
        ans = min(dist[n-1])
        
        return ans if ans < float('inf') else -1

C++ 程式碼

Runtime: 348 ms, beats 27.91%. Memory: 294.99 MB, beats 46.51%.

class Solution {
public:
    int shortestPath(int n, vector<vector<int>>& edges, string labels, int k) {
        // 特例，n 等於 0，不需要走
        if (n == 0) return 0;

        // 一般狀況，先用接鄰矩陣存有向圖
        vector<vector<pair<int, int>>> adj (n);
        for(auto edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            adj[u].push_back({v, w});
        }

        // Dijkstra 演算法，找走到各節點、各種末端連續相同字母數量對應的最低權重
        vector<vector<int>> dist (n, vector<int> (k+1, 1000000000));
        dist[0][1] = 0;  // 起點 
        
        // 最小優先佇列，{權重, 節點編號, 字母數量}
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
        pq.push({0, 0, 1});  // 權重 0，起點 0，數量 1
        while(!pq.empty()) {
            auto [w, u, cnt] = pq.top();
            pq.pop();
            for(auto it : adj[u]) {
                int v = it.first, d = it.second;
                int nxt = (labels[u] == labels[v] ? cnt + 1 : 1);
                if (nxt <= k && w + d < dist[v][nxt]) {
                    dist[v][nxt] = w + d;
                    pq.push({w + d, v, nxt});
                }
            }
        }

        int ans = *min_element(dist[n-1].begin(), dist[n-1].end());
        return (ans < 1000000000 ? ans : -1);
    }
};