题目链接： https://leetcode-cn.com/problems/shortest-path-with-alternating-colors/
首发：广度优先搜索，C++实现
解题思路
使用两路搜索路径，分别对两种颜色同时进行搜索。即：在初始化队列时分别将0节点分别以两种颜色加入到队列中
代码
class Solution {
public:
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
/* 经典bfs，构造队列 */
queue<pair<int, bool>> edgeQ;
vector<bool> redM(redEdges.size(),false);
vector<bool> blueM(blueEdges.size(),false);
vector<int> dist(n, INT_MAX);
/* 两种颜色同时搜索 */
edgeQ.push({0,false});
edgeQ.push({0,true});
int depth = 0;
while(!edgeQ.empty()){
int size = edgeQ.size();
for(int i=0;i<size;i++){
auto [node, color] = edgeQ.front();
/* 更新最小距离 */
dist[node] = min(dist[node], depth);
if(color == false){
for(int j=0;j<redEdges.size();j++){
if(redEdges[j][0] == node and !redM[j]){
edgeQ.push({redEdges[j][1],true});
redM[j] = true;
}}}
else
{
for(int j=0;j<blueEdges.size();j++){
if(blueEdges[j][0] == node and !blueM[j]){
edgeQ.push({blueEdges[j][1],false});
blueM[j] = true;
}}}
edgeQ.pop();
}
depth++;
}
for (int i = 0; i < n; i++) {
if (dist[i] == INT_MAX) {
dist[i] = -1;
}
}
return dist;
}
};
结果
执行用时：16 ms, 在所有 C++ 提交中击败了81.03%的用户
内存消耗：13.5 MB, 在所有 C++ 提交中击败了87.93%的用户
