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

1.题目基本信息

1.1.题目描述

给定一个整数 n，即有向图中的节点数，其中节点标记为 0 到 n – 1。图中的每条边为红色或者蓝色，并且可能存在自环或平行边。

给定两个数组 redEdges 和 blueEdges，其中：

• redEdges[i] = [a_i, b_i] 表示图中存在一条从节点 a_i 到节点 b_i 的红色有向边，
• blueEdges[j] = [u_j, v_j] 表示图中存在一条从节点 u_j 到节点 v_j 的蓝色有向边。

返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。

1.2.题目地址

https://leetcode.cn/problems/shortest-path-with-alternating-colors/description/

2.解题方法

2.1.解题思路

广度优先搜索

2.2.解题步骤

第一步，构建图邻接表。标记红色的边为0，蓝色的边为1。图结构：{起始点:[(目的点,边的颜色标识),…],…}

第二步，BFS遍历。对于子节点加入队列的条件中加上父节点和子节点的颜色标识之和为1，这样就能保证路径的颜色交替条件。同时在过程中记录递归层数，即为步数，记录到result数组中。

3.解题代码

Python代码

from collections import deque

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
        # BFS
        # 第一步，构建图邻接表。标记红色的边为0，蓝色的边为1。图结构：{起始点:[(目的点,边的颜色标识),...],...}
        graph=[[] for _ in range(n)]
        for edge in redEdges:
            graph[edge[0]].append((edge[1],0))
        for edge in blueEdges:
            graph[edge[0]].append((edge[1],1))
        # 第二步，BFS遍历。对于子节点加入队列的条件中加上父节点和子节点的颜色标识之和为1，这样就能保证路径的颜色交替条件。同时在过程中记录递归层数，即为步数，记录到result数组中。
        que=deque([(0,0,0),(0,1,0)])
        visited=set([(0,0),(0,1)])
        result=[-1]*n
        while que:
            curLength=len(que)
            for i in range(curLength):
                node,color,steps=que.popleft()
                result[node]=steps if result[node]==-1 else min(steps,result[node])
                for subNode,subColor in graph[node]:
                    if (subNode,subColor) not in visited and subColor+color==1:
                        visited.add((subNode,subColor))
                        que.append((subNode,subColor,steps+1))
        # print(result)
        return result

4.执行结果