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

Rust Solution

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
    );
}

Having problems with this solution? Click here to submit an issue on github.