129. 颜色交替的最短路径

题目链接：129. 颜色交替的最短路径

方法：BFS

解题思路

• 当边的权重为 \(1\) 时，可以使用 \(BFS\) 计算最短路径；
• 因为起始边有两种情况，所以都需要计算，最后取两者的最小值；

代码

class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        // 初始化两种颜色的邻接链表
        vector<vector<vector<int>>> next(2, vector<vector<int>>(n));
        for (auto &e : redEdges) next[0][e[0]].push_back(e[1]); // 红色邻接链表——0
        for (auto &e : blueEdges) next[1][e[0]].push_back(e[1]); // 蓝色邻接链表——1

        // 从红色/蓝色边出发两种情况的最短路径距离
        vector<vector<int>> dist(2, vector<int>(n, INT_MAX));

        // 边的权重为1时，BFS最先搜索到的即为最短路径
        queue<pair<int, int>> q; // 其中pair<a, b>，a表示节点，b表示颜色
        dist[0][0] = 0;  // 初始化dist数组
        dist[1][0] = 0;
        q.push({0, 0});
        q.push({0, 1});
        while (!q.empty()) {
            auto [x, t] =  q.front();
            q.pop();
            for (auto y : next[1 - t][x]) {
                if (dist[1 - t][y] != INT_MAX) continue;
                dist[1 - t][y] = dist[t][x] + 1;
                q.push({y, 1 - t});
            }
        }

        // 计算两种情况中的最短路径距离
        vector<int> answer(n);
        for (int i = 0; i < n; i ++ ) {
            answer[i] = min(dist[0][i], dist[1][i]);
            if (answer[i] == INT_MAX) answer[i] = -1;
        }

        return answer;        
    }
};