LeetCode 1129. 颜色交替的最短路径

题目描述

有一个有向图，n 个节点编号从 0 到 n-1。图中有两种颜色的有向边：红色和蓝色。每条红色边由 redEdges[i] = [a_i, b_i] 表示，表示从节点 a_i 到节点 b_i 的红色有向边；每条蓝色边由 blueEdges[i] = [u_i, v_i] 表示，表示从节点 u_i 到节点 v_i 的蓝色有向边。

题目要求：从节点 0 出发到其他所有节点的最短路径，但路径必须满足颜色交替的规则：即每一步走的边的颜色必须与上一步边的颜色不同（第一步可以选择红色或蓝色边）。对于每个节点 i，需要求出在满足交替规则下的最短路径长度，如果不存在这样的路径，则结果为 -1。

解题过程

1. 理解核心难点

路径必须是颜色交替的，这意味着：

• 我们不能单纯地按普通 BFS 处理，因为我们需要记录到达某个节点时，最后一步走的是什么颜色的边。
• 下一步必须走另一种颜色的边。

这相当于在状态空间中搜索：状态 = (当前节点, 上一步边的颜色)。

2. 状态定义与图表示

我们把图用两个邻接表表示：

• g[0][u]：存储从 u 出发的红色边能到达的节点列表。
• g[1][u]：存储从 u 出发的蓝色边能到达的节点列表。

状态 (node, color) 表示：当前在节点 node，且上一步走的边颜色是 color（0 表示红色，1 表示蓝色）。
特殊地，起点 0 时，我们可以认为上一步颜色是 0 或 1（即第一步可以选红或蓝），也可以单独用 color = -1 表示没有上一步，两种方法都可以处理。

3. BFS 搜索设计

我们使用 BFS 寻找最短路径长度，因为边权均为 1（每走一步长度+1）。

队列元素：(节点, 上一步颜色)
距离数组：dist[node][color] 表示到达节点 node 且上一步颜色为 color 的最短路径长度。初始化为无穷大。
初始状态：从节点 0 开始，可以认为上一步颜色为 0 或 1 都可出发，所以将 (0, 0) 和 (0, 1) 都加入队列，dist[0][0] = dist[0][1] = 0。

BFS 过程：

1. 弹出 (u, lastColor)。
2. 当前应该走的边颜色是 nextColor = 1 - lastColor（因为要交替）。
3. 遍历 g[nextColor][u] 中的每个邻居 v。
4. 如果 dist[v][nextColor] 还未被访问（即无穷大），则更新距离并加入队列。
5. 继续直到队列为空。

4. 最终答案

对于每个节点 i，合法的到达状态是 dist[i][0] 和 dist[i][1] 中最小的一个（因为最后一步可以是红或蓝），如果两个都是无穷大，则答案为 -1。

5. 逐步示例

假设：

n = 3
redEdges = [[0,1],[1,2]]
blueEdges = [[0,1]]

表示：

• 红边：0→1，1→2
• 蓝边：0→1

BFS 过程（手工模拟）：

1. 初始队列：[(0,0), (0,1)]，距离 dist[0][0]=0, dist[0][1]=0。
2. 弹出 (0,0)，上一步红色，下一步必须蓝色。蓝色边从 0 出发只有到 1，所以到 (1, 蓝)，距离 1。队列加入 (1,1)。
3. 弹出 (0,1)，上一步蓝色，下一步必须红色。红色边从 0 出发到 1，所以到 (1, 红)，距离 1。队列加入 (1,0)。
4. 弹出 (1,1)，上一步蓝色，下一步红色。红色边从 1 出发到 2，到 (2, 红) 距离 2。队列加入 (2,0)。
5. 弹出 (1,0)，上一步红色，下一步蓝色。蓝色边从 1 出发没有，所以无新状态。
6. 弹出 (2,0)，上一步红色，下一步蓝色。蓝色边从 2 出发没有，结束。

最终：

• 节点 0：min(dist[0][0], dist[0][1]) = 0
• 节点 1：min(1, 1) = 1
• 节点 2：min(2, ∞) = 2

结果：[0, 1, 2]。

6. 边界情况

• 如果从 0 出发没有红边也没有蓝边，则只有节点 0 答案为 0，其他为 -1。
• 可能存在自环，不影响交替规则，但距离会更新。
• 红边和蓝边可能有平行边（相同颜色或不同颜色），按正常邻接表处理即可。

7. 代码框架

from collections import deque

def shortestAlternatingPaths(n, redEdges, blueEdges):
    # 构建邻接表
    g = [ [[] for _ in range(n)] for _ in range(2) ]  # 0: red, 1: blue
    for u, v in redEdges:
        g[0][u].append(v)
    for u, v in blueEdges:
        g[1][u].append(v)
    
    dist = [[float('inf')] * 2 for _ in range(n)]
    dist[0][0] = dist[0][1] = 0
    
    q = deque()
    q.append((0, 0))  # (node, lastColor)
    q.append((0, 1))
    
    while q:
        u, last = q.popleft()
        next_color = 1 - last
        for v in g[next_color][u]:
            if dist[v][next_color] == float('inf'):
                dist[v][next_color] = dist[u][last] + 1
                q.append((v, next_color))
    
    res = []
    for i in range(n):
        d = min(dist[i][0], dist[i][1])
        res.append(d if d != float('inf') else -1)
    return res

8. 复杂度分析

• 时间复杂度：O(n + r + b)，其中 r 和 b 分别是红边和蓝边的数量。
• 空间复杂度：O(n + r + b)，用于存储邻接表和距离数组。

这个算法本质上是状态扩展的 BFS，将颜色信息纳入状态，从而将约束条件转化为状态转移的条件，是处理带约束最短路径问题的经典思路。