Shortest Path with Alternating Colors
Problem Statement - link #
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.
Examples #
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 < n
Solutions #
class Solution {
public:
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
vector<int> res(n, -1);
vector<vector<pair<int, int>>> g(n);
queue<pair<int, int>> q;
q.push({0, -1});
for(const auto &it: redEdges) {
g[it[0]].push_back({it[1], 0});
}
for(const auto &it: blueEdges) {
g[it[0]].push_back({it[1], 1});
}
int temp = 0;
while(q.size()) {
int s = q.size();
while(s--) {
const auto [u, pc] = q.front();
q.pop();
res[u] = (res[u] == -1) ? temp : res[u];
for(auto& [v, cc] : g[u]) {
if(v == -1 || pc == cc) {
continue;
}
q.push({v, cc});
v = -1;
}
}
temp++;
}
return res;
}
};