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, andblueEdges[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 <= 1000 <= redEdges.length, blueEdges.length <= 400redEdges[i].length == blueEdges[j].length == 20 <= ai, bi, uj, vj < nclass Solution {
public:
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {
vector<vector<pair<int,int>>> g(n); //index, {neighbor index, color}
for(auto& v:red_edges) g[v[0]].push_back({v[1], 0});
for(auto& v:blue_edges) g[v[0]].push_back({v[1], 1});
vector<vector<int>> vCost(n, vector<int>(2,-1));
queue<pair<int,int>> q; // index, color(0 or 1)
q.push({0,0});
q.push({0,1});
vCost[0] = {0,0};
while(!q.empty()){
auto [i, c1] = q.front(); q.pop();
for(auto [j, c2] : g[i]){
if(vCost[j][c2] != -1 || c1 == c2) continue;
vCost[j][c2] = 1 + vCost[i][c1];
q.push({j, c2});
}
}
vector<int> res;
for(auto& v : vCost) {
sort(v.begin(), v.end());
res.push_back(v[0] != -1 ? v[0] : v[1]);
}
return res;
}
};