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

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

方法思路

解决代码

import collectionsdef 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/