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.

class Solution {
    int gr[101][2];
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        memset(gr,-1,sizeof(gr));
        map<int, vector<int>> r, b;
        for(auto& e : redEdges) {
            r[e[0]].push_back(e[1]);
        }
        for(auto& e : blueEdges) {
            b[e[0]].push_back(e[1]);
        }
        
        queue<pair<int, int>> q;
        q.push({0, 0});
        q.push({0, 1});
        gr[0][0] = gr[0][1] = 0;
        while(!q.empty()) {
            auto p = q.front();
            q.pop();
            int nxtColor = p.second ? 0 : 1;
            if(p.second) {
                //blue
                for(auto nxt : b[p.first]) {
                    if(gr[nxt][nxtColor] == -1) {
                        q.push({nxt, nxtColor});
                        gr[nxt][nxtColor] = gr[p.first][p.second] + 1;
                    }
                }
            } else {
                //red
                for(auto nxt : r[p.first]) {
                    if(gr[nxt][nxtColor] == -1) {
                        q.push({nxt, nxtColor});
                        gr[nxt][nxtColor] = gr[p.first][p.second] + 1;
                    }
                }
            }
        }
        
        vector<int> res(n, -1);
        res[0] = 0;
        for(int i = 1; i < n; i++) {
            int rc = gr[i][0];
            int bc = gr[i][1];
            if(rc != -1 and bc != -1) res[i] = min(rc, bc);
            else if(rc != -1) res[i] = rc;
            else if(bc != -1) res[i] = bc;
        }

        return res;
    }
};