建设银行贵阳市网站电话,做地方的门户网站,网站创建服务公司,wordpress用哪个版本今日份题目#xff1a;
给定一个整数 n#xff0c;即有向图中的节点数#xff0c;其中节点标记为 0 到 n - 1。图中的每条边为红色或者蓝色#xff0c;并且可能存在自环或平行边。
给定两个数组 redEdges 和 blueEdges#xff0c;其中#xff1a; redEdges[i] [ai, bi…今日份题目
给定一个整数 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:vectorint shortestAlternatingPaths(int n, vectorvectorint redEdges, vectorvectorint blueEdges) {vectorvectorvectorint next(2,vectorvectorint (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]);//第二个二维表存放蓝边信息}vectorvectorint dist(2,vectorint(n,INT_MAX)); //两种类型的颜色最短路径的长度queuepairint, int p;dist[0][0]0;dist[1][0]0;p.push({0,0});//第一个表的0p.push({0,1});//第二个表的0while(!p.empty()) {int xyp.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});}}vectorint ans(n);for(int i0;in;i) {ans[i]min(dist[0][i],dist[1][i]);//两个图中最小的路径长if(ans[i]INT_MAX) //不存在置为-1{ans[i]-1;}}return ans;}
};提交结果 欢迎大家在评论区讨论如有不懂的代码部分欢迎在评论区留言
