題目鏈接： https://leetcode-cn.com/problems/shortest-path-with-alternating-colors/
首發(fā)：廣度優(yōu)先搜索，C++實(shí)現(xiàn)

解題思路

使用兩路搜索路徑，分別對兩種顏色同時(shí)進(jìn)行搜索。即：在初始化隊(duì)列時(shí)分別將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);
        /* 兩種顏色同時(shí)搜索 */
        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í)行用時(shí)：16 ms, 在所有 C++ 提交中擊敗了81.03%的用戶
內(nèi)存消耗：13.5 MB, 在所有 C++ 提交中擊敗了87.93%的用戶