README.md

1129. Shortest Path with Alternating Colors

You are given an integer n, the number of nodes in a directed graph where the nodes are labeled from 0 to n - 1. Each edge is red or blue in this graph, and there could be self-edges and parallel edges.

You are given two arrays redEdges and blueEdges where:

• redEdges[i] = [ai, bi] indicates that there is a directed red edge from node ai to node bi in the graph, and
• blueEdges[j] = [uj, vj] indicates that there is a directed blue edge from node uj to node vj in the graph.

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 does not exist.

Example 1:

Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]

Example 2:

Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output: [0,1,-1]

Constraints:

• 1 <= n <= 100
• 0 <= redEdges.length, blueEdges.length <= 400
• redEdges[i].length == blueEdges[j].length == 2
• 0 <= ai, bi, uj, vj < n

Solutions (Rust)

1. Solution

use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::collections::HashSet;

impl Solution {
    pub 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 red_nexts = vec![vec![]; n];
        let mut blue_nexts = vec![vec![]; n];
        let mut nodes_heap = BinaryHeap::from([(Reverse(0), 0, true), (Reverse(0), 0, false)]);
        let mut visited = HashSet::new();
        let mut answer = vec![(i32::MAX, i32::MAX); n];
        answer[0] = (0, 0);

        for edge in &red_edges {
            red_nexts[edge[0] as usize].push(edge[1] as usize);
        }
        for edge in &blue_edges {
            blue_nexts[edge[0] as usize].push(edge[1] as usize);
        }

        while let Some((Reverse(length), node, is_red)) = nodes_heap.pop() {
            if visited.contains(&(node, is_red)) {
                continue;
            }

            visited.insert((node, is_red));

            if is_red {
                for &next in &blue_nexts[node] {
                    if answer[next].1 > length + 1 {
                        answer[next].1 = length + 1;
                        nodes_heap.push((Reverse(length + 1), next, false));
                    }
                }
            } else {
                for &next in &red_nexts[node] {
                    if answer[next].0 > length + 1 {
                        answer[next].0 = length + 1;
                        nodes_heap.push((Reverse(length + 1), next, true));
                    }
                }
            }
        }

        answer
            .into_iter()
            .map(|(red, blue)| {
                if red.min(blue) == i32::MAX {
                    -1
                } else {
                    red.min(blue)
                }
            })
            .collect()
    }
}