文章目录
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:
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
);
bfs(r
,b
,1,dis
);
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
++;
flag
= !flag
;
}
}
};
36 ms 13.6 MB
我的博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
