跳转至

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

1、题目描述

在一个有向图中,节点分别标记为 0, 1, ..., n-1。这个图中的每条边不是红色就是蓝色,且存在自环或平行边。

red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。类似地,blue_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的蓝色有向边。

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

示例 1:

输入:n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
输出:[0,1,-1]

示例 2:

输入:n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
输出:[0,1,-1]

示例 3:

输入:n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
输出:[0,-1,-1]

示例 4:

输入:n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
输出:[0,1,2]

示例 5:

输入:n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
输出:[0,1,1]

提示:

  • 1 <= n <= 100
  • red_edges.length <= 400
  • blue_edges.length <= 400
  • red_edges[i].length == blue_edges[i].length == 2
  • 0 <= red_edges[i][j], blue_edges[i][j] < n

2、解题思路

  • 使用广度优先搜索
  • 0点开始搜索,每一个点需要一个颜色属性,表示这个点前面从什么颜色的边过来,下一条边的搜索将是另一种颜色的边
(0,0)  => 节点0,上次的边颜色为红色,下一条边为蓝色
(0,1)  => 节点0,上次的边颜色为蓝色,下一条边为红色
from collections import defaultdict


class Solution:
    def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
        visited = set()
        ans = [-1] * n
        ans[0] = 0

        mapping = {
            0: defaultdict(set),
            1: defaultdict(set)
        }

        for x, y in red_edges:
            mapping[0][x].add(y)
        for x, y in blue_edges:
            mapping[1][x].add(y)

        # (node,color)
        visited.add((0, 0))
        visited.add((0, 1))
        d = [(0, 0), (0, 1)]

        step = 0
        while d:
            step += 1
            next_d = []
            for node, color in d:
                for next_node in mapping[color ^ 1][node]:
                    if (next_node, color ^ 1) not in visited:
                        visited.add((next_node, color ^ 1))
                        next_d.append((next_node, color ^ 1))
                        if ans[next_node] == -1:
                            ans[next_node] = step
            d = next_d

        return ans