MediumRating 1780
1129. Shortest Path with Alternating Colors
breadth-first-searchgraph
解題說明
Shortest Path with Alternating Colors
題目描述：
給定一個有向圖，有 n 個節點（0 到 n-1）。邊有兩種顏色：紅色和藍色。從節點 0 出發，找到到每個節點的最短路徑長度，但路徑中的邊顏色必須交替出現（紅、藍、紅、藍... 或 藍、紅、藍、紅...）。若無法到達某節點，返回 -1。
解題思路： BFS + 狀態擴展：
狀態定義：(node, lastColor)。因為同一個節點可能經由不同顏色的最後一條邊到達，且後續可走的邊不同。
- 建立兩個鄰接表：
redAdj[u]和blueAdj[u]。 - BFS 從兩個起始狀態開始：
(0, RED)和(0, BLUE)（距離 0）。 - 每一步：若最後一條邊是紅色，則下一步走藍色邊；反之亦然。
- 用
dist[node][color]記錄最短距離，避免重複訪問。 - 答案：
min(dist[node][RED], dist[node][BLUE])。
C++ 解法
複雜度分析
時間複雜度：O(n + E) — 其中 E 是邊的總數（紅 + 藍）。BFS 中每個 (node, color) 狀態最多被處理一次。
空間複雜度：O(n + E) — 鄰接表和距離陣列。
虛擬碼
1. Build adjacency lists for red edges and blue edges.
2. Initialize dist[n][2] = INF; dist[0][0] = dist[0][1] = 0.
3. BFS queue starts with (0, RED) and (0, BLUE).
4. While queue not empty:
a. Dequeue (node, color).
b. nextColor = 1 - color.
c. For each neighbor via nextColor edges:
If dist[node][color] + 1 < dist[neighbor][nextColor]:
Update distance, enqueue (neighbor, nextColor).
5. For each node: result = min(dist[node][0], dist[node][1]), or -1 if INF.其他解法
Dijkstra 變體：O((n + E) log n) 時間。用優先佇列代替普通佇列。但因為所有邊權為 1，BFS 已是最優，Dijkstra 反而更慢。
分層圖 BFS：O(n + E) 時間。將圖拆成兩層（紅邊層和藍邊層），每層之間交替連接。概念上更清晰但實作需要更多空間。
延伸思考
- 為什麼狀態需要包含「最後一條邊的顏色」？只記錄節點是否足夠？
- 如果邊有三種顏色（紅、藍、綠），且要求連續三條邊顏色都不同，狀態空間如何擴展？
- 如果邊有權重（不全是 1），BFS 是否還適用？需要改用什麼演算法？