# 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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1129.shortest-path-with-alternating-colors.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.