LeetCode 1129. 颜色交替的最短路径（BFS）

示例 1：
输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
输出：[0,1,-1]

示例 2：
输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
输出：[0,1,-1]

示例 3：
输入：n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
输出：[0,-1,-1]

示例 4：
输入：n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
输出：[0,1,2]

示例 5：
输入：n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
输出：[0,1,1]
 
提示：
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

class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {
    	vector<vector<int>> dis(2, vector<int>(n, INT_MAX));
    	vector<vector<int>> r(n), b(n);
    	for(auto& e : red_edges)
    		r[e[0]].push_back(e[1]);
    	for(auto& e : blue_edges)
    		b[e[0]].push_back(e[1]);//建图
    	bfs(r,b,0,dis);//出发，case1
    	bfs(r,b,1,dis);//出发，case2
    	vector<int> ans(n,-1);
    	for(int i = 0; i < n; ++i)
    	{
    		ans[i] = min(dis[0][i], dis[1][i]);
    		if(ans[i] == INT_MAX)
    			ans[i] = -1;
    	}
    	return ans;
    }

    void bfs(vector<vector<int>>& r, vector<vector<int>>& b, int flag, vector<vector<int>>& dis)
    {
    	int n = r.size(), cur, size, step = 0;
    	vector<vector<bool>> vis(2, vector<bool>(n, false));//访问标记
    	queue<int> q;
    	q.push(0);
    	vis[flag][0] = true;
    	while(!q.empty())
    	{
    		size = q.size();
    		while(size--)
    		{
    			cur = q.front();
    			dis[flag][cur] = min(dis[flag][cur], step);//取最小的路径
    			q.pop();
    			if(flag)//走红色的
    			{
    				for(auto nt : r[cur])
    				{
    					if(vis[flag][nt])//访问过了，不能再次访问
    						continue;
    					vis[flag][nt] = true;
    					q.push(nt);
    				}
    			}
    			else//走蓝色的
    			{
    				for(auto nt : b[cur])
    				{
    					if(vis[flag][nt])
    						continue;
    					vis[flag][nt] = true;
    					q.push(nt);
    				}
    			}
    		}
    		step++;//步数+1
    		flag = !flag;//换地图颜色
    	}
    }
};