Leetcode 1129：颜色交替的最短路径（超详细的解法！！！）

最新推荐文章于 2024-02-05 21:31:05 发布

coordinate_blog

最新推荐文章于 2024-02-05 21:31:05 发布

阅读量2k

点赞数

分类专栏： Problems leetcode解题指南文章标签： leetcode

本文链接：https://blog.csdn.net/qq_17550379/article/details/97003669

版权

在一个有向图中，节点分别标记为 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]

提示：

解题思路

最短路径问题，那么直接使用bfs即可。由于问题给的是一系列点，那么我们首先想到通过构建邻接表的方式构建图。但是这个问题有一个难点在于颜色交替，这就很麻烦了，所以我们必须先将问题转化为一般的bfs问题。怎么转呢？可以建立两个图，一个是红色的，一个是蓝色的，然后根据不同颜色的图去遍历结果即可。

首先构建图

g0, g1 = collections.defaultdict(list), collections.defaultdict(list)
for i, j in red_edges:
    g0[i].append(j)
for i, j in