1129. 颜色交替的最短路径

题目链接： 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%的用户