題目鏈接： https://leetcode-cn.com/problems/shortest-path-with-alternating-colors/
首發(fā)：廣度優(yōu)先搜索他托，C++實(shí)現(xiàn)
解題思路
使用兩路搜索路徑糙麦，分別對兩種顏色同時進(jìn)行搜索唱蒸。即：在初始化隊(duì)列時分別將0節(jié)點(diǎn)分別以兩種顏色加入到隊(duì)列中
代碼
class Solution {
public:
vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
/* 經(jīng)典bfs，構(gòu)造隊(duì)列 */
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;
}
};
結(jié)果
執(zhí)行用時：16 ms, 在所有 C++ 提交中擊敗了81.03%的用戶
內(nèi)存消耗：13.5 MB, 在所有 C++ 提交中擊敗了87.93%的用戶
