題目描述:
給定一個有向圖,有 n 個節點(0 到 n-1)。邊有兩種顏色:紅色和藍色。從節點 0 出發,找到到每個節點的最短路徑長度,但路徑中的邊顏色必須交替出現(紅、藍、紅、藍... 或 藍、紅、藍、紅...)。若無法到達某節點,返回 -1。
解題思路: BFS + 狀態擴展:
狀態定義:(node, lastColor)。因為同一個節點可能經由不同顏色的最後一條邊到達,且後續可走的邊不同。
redAdj[u] 和 blueAdj[u]。(0, RED) 和 (0, BLUE)(距離 0)。dist[node][color] 記錄最短距離,避免重複訪問。min(dist[node][RED], dist[node][BLUE])。時間複雜度: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) 時間。將圖拆成兩層(紅邊層和藍邊層),每層之間交替連接。概念上更清晰但實作需要更多空間。