1129. Shortest Path with Alternating Colors
给 n 个点，红色的有向边，蓝色的有向边，可能包含自环或是重边(颜色不同)，
求从 0 号点出发，用交错边到每个点的最短路径，若无法到达则是-1。
Example 1:
Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]
Explanation: 从 0 号点只能从红边到 1 号点，没有蓝边可以继续前往 2 号点
Example 2:
Input: n = 3, redEdges = [[0,1]], blueEdges = [[2,1]]
Output: [0,1,-1]
Explanation: 从 0 号点到 1 号点后，蓝边[2, 1]是有向边，无法从 1 号到 2 号
解题思路：
对于每个点纪录由红边到达以及蓝边到达的最短路径，
把存边的资料结构改成 adjacency lists 会比较容易存取，
从 0 号点开始进行 BFS，出发的边可以是红边也可以是蓝边，
如果是用红边到达的点就用蓝边来更新邻居，蓝边就反过来，
每个点最多只会被更新 2 次。
C++ code:
#define RED 0
#define BLUE 1
class Solution {
public:
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>&
redEdges, vector<vector<int>>& blueEdges) {
vector<vector<int>> dis(n, {INT_MAX, INT_MAX});
vector<vector<int>> red(n, vector<int>()), blue(n, vector<int>());
for(auto i : redEdges)
red[i[0]].push_back(i[1]);
for(auto i : blueEdges)
blue[i[0]].push_back(i[1]);
dis[0] = {0, 0};
queue<pair<int, int>> que; // {node, color}
que.push({0, RED});
que.push({0, BLUE});
while(que.size() > 0){
auto [id, color] = que.front(); que.pop();
if(color == RED){
for(auto i : blue[id]){
if(dis[id][RED] + 1 < dis[i][BLUE]){
dis[i][BLUE] = dis[id][RED] + 1;
que.push({i, BLUE});
}
}
}
else{
for(auto i : red[id]){
if(dis[id][BLUE] + 1 < dis[i][RED]){
dis[i][RED] = dis[id][BLUE] + 1;
que.push({i, RED});
}
}
}
}
vector<int> ans(n);
for(int i = 0; i < n; i++){
ans[i] = min(dis[i][RED], dis[i][BLUE]);
if(ans[i] == INT_MAX) ans[i] = -1;
}
return ans;
}
};