# 1129. Shortest Path with Alternating Colors

Consider a directed graph, with nodes labelled `0, 1, ..., n-1`.  In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.

Each `[i, j]` in `red_edges` denotes a red directed edge from node `i` to node `j`.  Similarly, each `[i, j]` in `blue_edges` denotes a blue directed edge from node `i` to node `j`.

Return an array `answer` of length `n`, where each `answer[X]` is the length of the shortest path from node `0` to node `X` such that the edge colors alternate along the path (or `-1` if such a path doesn’t exist).

Example 1:

``````Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]
``````

Example 2:

``````Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
Output: [0,1,-1]
``````

Example 3:

``````Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
Output: [0,-1,-1]
``````

Example 4:

``````Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
Output: [0,1,2]
``````

Example 5:

``````Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
Output: [0,1,1]
``````

Constraints:

• `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`

``````class Solution {
public:
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {
vector<int> res(n);
vector<vector<int>> dp(2, vector<int>(n));
vector<vector<unordered_set<int>>> graph(2, vector<unordered_set<int>>(n));
for (auto &edge : red_edges) {
graph[0][edge[0]].insert(edge[1]);
}
for (auto &edge : blue_edges) {
graph[1][edge[0]].insert(edge[1]);
}
for (int i = 1; i < n; ++i) {
dp[0][i] = 2 * n;
dp[1][i] = 2 * n;
}
queue<vector<int>> q;
q.push({0, 0});
q.push({0, 1});
while (!q.empty()) {
int cur = q.front()[0], color = q.front()[1]; q.pop();
for (int next : graph[1 - color][cur]) {
if (dp[1 - color][next] == 2 * n) {
dp[1 - color][next] = 1 + dp[color][cur];
q.push({next, 1 - color});
}
}
}
for (int i = 0; i < n; ++i) {
int val = min(dp[0][i], dp[1][i]);
res[i] = val == 2 * n ? -1 : val;
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1129

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

https://leetcode.com/problems/shortest-path-with-alternating-colors/discuss/339964/JavaPython-BFS

https://leetcode.com/problems/shortest-path-with-alternating-colors/discuss/340258/Java-BFS-Solution-with-Video-Explanation

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation