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

1129. Shortest Path with Alternating Colors
struct Solution;
use std::collections::VecDeque;

impl Solution {
fn shortest_alternating_paths(
n: i32,
red_edges: Vec<Vec<i32>>,
blue_edges: Vec<Vec<i32>>,
) -> Vec<i32> {
let n = n as usize;
let mut graph: Vec<Vec<Vec<usize>>> = vec![vec![vec![]; n]; 2];
let mut visited: Vec<Vec<bool>> = vec![vec![false; n]; 2];
let mut res: Vec<i32> = vec![-1; n];
for e in red_edges {
let u = e[0] as usize;
let v = e[1] as usize;
graph[0][u].push(v);
}
for e in blue_edges {
let u = e[0] as usize;
let v = e[1] as usize;
graph[1][u].push(v);
}
let mut queue: VecDeque<(usize, usize, usize)> = VecDeque::new();
queue.push_back((0, 0, 0));
queue.push_back((0, 1, 0));
visited[0][0] = true;
visited[1][0] = true;
while let Some((u, c, d)) = queue.pop_front() {
if res[u] == -1 {
res[u] = d as i32;
}
for &v in &graph[c][u] {
if !visited[1 - c][v] {
visited[1 - c][v] = true;
queue.push_back((v, 1 - c, d + 1));
}
}
}
res
}
}

#[test]
fn test() {
let n = 3;
let red_edges = vec_vec_i32![[0, 1], [1, 2]];
let blue_edges = vec_vec_i32![];
let res = vec![0, 1, -1];
assert_eq!(
Solution::shortest_alternating_paths(n, red_edges, blue_edges),
res
);
let n = 3;
let red_edges = vec_vec_i32![[0, 1]];
let blue_edges = vec_vec_i32![[2, 1]];
let res = vec![0, 1, -1];
assert_eq!(
Solution::shortest_alternating_paths(n, red_edges, blue_edges),
res
);
let n = 3;
let red_edges = vec_vec_i32![[1, 0]];
let blue_edges = vec_vec_i32![[2, 1]];
let res = vec![0, -1, -1];
assert_eq!(
Solution::shortest_alternating_paths(n, red_edges, blue_edges),
res
);
let n = 3;
let red_edges = vec_vec_i32![[0, 1]];
let blue_edges = vec_vec_i32![[1, 2]];
let res = vec![0, 1, 2];
assert_eq!(
Solution::shortest_alternating_paths(n, red_edges, blue_edges),
res
);
let n = 3;
let red_edges = vec_vec_i32![[0, 1], [0, 2]];
let blue_edges = vec_vec_i32![[1, 0]];
let res = vec![0, 1, 1];
assert_eq!(
Solution::shortest_alternating_paths(n, red_edges, blue_edges),
res
);
}