1129

1129. Shortest Path with Alternating Colors (Medium)

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

Companies:
Amazon, Wish

Related Topics:
Breadth-first Search, Graph

Solution 1. BFS

// OJ: https://leetcode.com/problems/shortest-path-with-alternating-colors/
// Author: github.com/lzl124631x
// Time: O(R + B + N^2)
// Space: O(N^2)
class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& R, vector<vector<int>>& B) {
        vector<int> a(n, -1), b(n, -1), ans(n, -1);
        a[0] = b[0] = ans[0] = 0;
        int G[100][100] = {};
        for (auto &r : R) G[r[0]][r[1]] = 1;
        for (auto &b : B) G[b[0]][b[1]] |= 2;
        queue<pair<int, int>> q;
        q.emplace(0, 3);
        int step = 1;
        while (q.size()) {
            int cnt = q.size();
            while (cnt--) {
                auto [u, color] = q.front();
                q.pop();
                for (int v = 0; v < n; ++v) {
                    if (a[v] == -1 && (G[u][v] & 1) && (color & 2)) {
                        q.emplace(v, 1);
                        a[v] = step;
                        ans[v] = ans[v] == -1 ? a[v] : min(a[v], ans[v]);
                    }
                    if (b[v] == -1 && (G[u][v] & 2) && (color & 1)) {
                        q.emplace(v, 2);
                        b[v] = step;
                        ans[v] = ans[v] == -1 ? b[v] : min(b[v], ans[v]);
                    }
                }
            }
            ++step;
        }
        return ans;
    }
};