> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1129.shortest-path-with-alternating-colors.md).
# 1129. 颜色交替的最短路径
### 题目地址(1129. 颜色交替的最短路径)
### 题目描述
```
在一个有向图中，节点分别标记为 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
```
### 前置知识
* BFS
### 公司
* 暂无
### 思路
如果这道题不是求从 0 到 i 的红蓝相间的最短路径长度，而是**从 0 到 i 的最短红色最短路径长度**， 你会求解么？
实际上，这就 变成了一个简单的 BFS。
我们只需要根据 red\_edges 建立邻接矩阵。接下来使用常规的 BFS 从 0 开始遍历，每遍历到一个节点就将其更新到答案中去即可。
那么问题扩展到红蓝相间有什么不同呢？不难发现，当本次边是红色的时候，下次我们需要从相邻的边中挑选一个蓝的边。如果本次是蓝色的边，则需要下次挑选一个红色的边。
这提示我们记录当前需要挑选的边的颜色是什么（红还是蓝）。
最直接的想法是建立两个队列。
* 一个是以红色边开始
* 另一个是以蓝色边开始
如果是蓝色边开始，显然需要从 blue\_edges 建立的临界矩阵中挑一个蓝色的边。挑选完毕之后，我们需要下次再挑选红色的边，以此类推。如果从红色边开始也是类似的，不再分析。
实际上，我们也可以使用一个队列。队列中存储的不是单一值，而是一个元祖，这样我们就可以将**当前的边颜色**信息存储到队列中。这样每次从队列中 pop 一个出来，就可直接根据 pop 出来的颜色来决定应该去红色边还是蓝色边了。
这里我使用 1 和 - 1 这样的一对相反数分别表示红色和蓝色，这样我就可以直接取相反数得到下一次 push 进队列的颜色是什么，而不用谢 if else 语句。
### 关键点
*
### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
ans = [2 * n] * n
neibors_red = collections.defaultdict(list)
neibors_blue = collections.defaultdict(list)
# 1. 建立邻接矩阵
for fr, to in red_edges:
neibors_red[fr].append(to)
for fr, to in blue_edges:
neibors_blue[fr].append(to)‘
# 将颜色也存入到队中
q = collections.deque([(0, -1), (0, 1)])
steps = 0
while q:
for _ in range(len(q)):
cur, color = q.popleft()
ans[cur] = min(ans[cur], steps)
# color == 1 该取红边了，否则取蓝边
neibors = neibors_red if color == 1 else neibors_blue
for nxt in neibors[cur]:
q.append((nxt, -1 * color))
# 此处的作用等同于 visited，即防止环的产产生。
neibors[cur] = []
steps += 1
return [-1 if a == 2 * n else a for a in ans]
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n)$
* 空间复杂度：$O(n)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
