日期：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);
}
};
