本文共 1990 字，大约阅读时间需要 6 分钟。

为了解决这个问题，我们需要找到从节点0到每个节点X的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，则返回-1。

方法思路

解决代码

import collections
def shortestAlternatingPaths(n, red_edges, blue_edges):
    if n == 0:
        return []
    
    # 创建红色和蓝色边的邻接表
    red_graph = collections.defaultdict(list)
    blue_graph = collections.defaultdict(list)
    for u, v in red_edges:
        red_graph[u].append(v)
    for u, v in blue_edges:
        blue_graph[u].append(v)
    
    # 初始化结果数组，路径长度为无穷大
    INF = float('inf')
    res = [[INF] * 2 for _ in range(n)]
    res[0][0] = 0  # 从0出发，路径初始为0，颜色红色
    res[0][1] = 0  # 从0出发，路径初始为0，颜色蓝色
    
    # 使用双端队列来处理BFS
    queue = collections.deque()
    queue.append((0, 0))  # (节点, 上一步的颜色)
    queue.append((0, 1))
    
    while queue:
        u, c = queue.popleft()
        current_dist = res[u][c]
        
        # 下一步颜色必须与当前颜色交替
        next_c = 1 - c
        
        # 根据当前颜色决定使用哪个邻接表
        if c == 0:
            # 下一步必须用蓝色边，对应的邻接表是blue_graph
            for v in blue_graph[u]:
                if res[v][next_c] > current_dist + 1:
                    res[v][next_c] = current_dist + 1
                    queue.append((v, next_c))
        else:
            # 下一步必须用红色边，对应的邻接表是red_graph
            for v in red_graph[u]:
                if res[v][next_c] > current_dist + 1:
                    res[v][next_c] = current_dist + 1
                    queue.append((v, next_c))
    
    # 构建答案数组
    ans = []
    for i in range(n):
        min_dist = min(res[i][0], res[i][1])
        if min_dist == INF:
            ans.append(-1)
        else:
            ans.append(min_dist)
    return ans

代码解释

这种方法确保了在交替颜色的约束下，高效地找到最短路径。

转载地址：http://vagr.baihongyu.com/