每天一道leetcode：1129. 颜色交替的最短路径（图论中等广度优先遍历）

今日份题目：

给定一个整数 n，即有向图中的节点数，其中节点标记为 0 到 n - 1。图中的每条边为红色或者蓝色，并且可能存在自环或平行边。

给定两个数组 redEdges 和 blueEdges，其中：

redEdges[i] = [ai, bi] 表示图中存在一条从节点 ai 到节点 bi 的红色有向边，
blueEdges[j] = [uj, vj] 表示图中存在一条从节点 uj 到节点 vj 的蓝色有向边。

返回长度为 n 的数组 answer，其中 answer[X] 是从节点 0 到节点 X 的红色边和蓝色边交替出现的最短路径的长度。如果不存在这样的路径，那么 answer[x] = -1。

示例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]

提示

1 <= n <= 100
0 <= redEdges.length, blueEdges.length <= 400
redEdges[i].length == blueEdges[j].length == 2
0 <= ai, bi, uj, vj < n

题目思路

依旧是使用bfs广度优先遍历，详细过程可看代码中的注释。

本道题目主要是注意细节，比如三维表next、二维表dist等等。

代码

class Solution 
{
public:vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {vector<vector<vector<int> > > next(2,vector<vector<int> >(n));for(auto &e:redEdges) {next[0][e[0]].push_back(e[1]);//第一个二维表存放红边信息}for(auto &e:blueEdges) {next[1][e[0]].push_back(e[1]);//第二个二维表存放蓝边信息}vector<vector<int> > dist(2,vector<int>(n,INT_MAX)); //两种类型的颜色最短路径的长度queue<pair<int, int> > p;dist[0][0]=0;dist[1][0]=0;p.push({0,0});//第一个表的0p.push({0,1});//第二个表的0while(!p.empty()) {int xy=p.front();p.pop();for(auto y:next[1-xy.second][xy.first]) //遍历当前点的邻接点{if(dist[1-xy.second][y]!=INT_MAX) //表示遍历过了{continue;}//实现交替路径dist[1-xy.second][y]=dist[xy.second][xy.first]+1;//另一个颜色的边数加一p.push({y,1-xy.second});}}vector<int> ans(n);for(int i=0;i<n;i++) {ans[i]=min(dist[0][i],dist[1][i]);//两个图中最小的路径长if(ans[i]==INT_MAX) //不存在，置为-1{ans[i]=-1;}}return ans;}
};