哈尔滨服务专业的建站,wordpress google font 360,网络营销推广服务商,贵阳网站建设q.479185700惠文章目录1. 题目2. 解题1. 题目
在一个有向图中#xff0c;节点分别标记为 0, 1, ..., n-1。 这个图中的每条边不是红色就是蓝色#xff0c;且存在自环或平行边。
red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。 类似地#xff0c;blue_edges 中的每…
文章目录1. 题目2. 解题1. 题目
在一个有向图中节点分别标记为 0, 1, ..., n-1。 这个图中的每条边不是红色就是蓝色且存在自环或平行边。
red_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的红色有向边。 类似地blue_edges 中的每一个 [i, j] 对表示从节点 i 到节点 j 的蓝色有向边。
返回长度为 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]示例 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来源力扣LeetCode 链接https://leetcode-cn.com/problems/shortest-path-with-alternating-colors 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
分两种情况从 0 出发红色或者蓝色每个点的访问标记 vis 有 2 个状态红的访问没蓝的访问没
class Solution {
public:vectorint shortestAlternatingPaths(int n, vectorvectorint red_edges, vectorvectorint blue_edges) {vectorvectorint dis(2, vectorint(n, INT_MAX));vectorvectorint 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);//出发case1bfs(r,b,1,dis);//出发case2vectorint 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(vectorvectorint r, vectorvectorint b, int flag, vectorvectorint dis){int n r.size(), cur, size, step 0;vectorvectorbool vis(2, vectorbool(n, false));//访问标记queueint 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;//步数1flag !flag;//换地图颜色}}
};36 ms 13.6 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
