1129.shortest-path-with-alternating-colors 颜色交替的最短路径

问题描述

1129.颜色交替的最短路径

解题思路

首先，将本题的图结构以边表的形式表现出来，然后采取广度优先搜索的方式寻找最短路径，一般来说广度优先搜索能够保证找到的是最短路径。

在本题中，由于要求最短路径是交替出现的，那么在判断节点是否已经访问过时，要分红色路径访问节点和蓝色路径访问节点两种情况讨论。

队列中的元素为三元组tie(point, len, c_flag)，分别表示当前节点的索引、到达当前节点的路径长度（不一定是最短的，本题中存在环）、到达当前节点的路径颜色（0表示蓝色，1表示红色）

提示bfs(q, red_connect, blue_connect, answer, n)（其中q包含tie(0, 0, 0)和tie(0, 0, 1)）与bfs(q, red_connect, blue_connect, answer, n)执行两次（q分别为tie(0, 0, 0)和tie(0, 0, 1)）的结果是一样的。

代码

class Solution {
  public:
    void bfs(queue<tuple<int, int, int>> q, vector<vector<int>> &red_connect, vector<vector<int>> &blue_connect, vector<int> &answer, int n, int i) {
        vector<vector<int>> visited(n, vector<int>(2, 0)); // visited[k][1]表示由红到point，visited[k][0]为1表示由蓝到point
        int tmp_point = 0;
        while (!q.empty()) {
            auto [point, len, c_flag] = q.front();
            visited[point][c_flag] = 1;
            q.pop();
            if (answer[point] == -1)
                answer[point] = len;
            else
                answer[point] = min(answer[point], len);
            if (c_flag == 0) {
                for (int k = 0; k < red_connect[point].size(); k++) {
                    tmp_point = red_connect[point][k];
                    if (visited[tmp_point][1] != 1)
                        q.push({tmp_point, len + 1, 1});
                }
            } else {
                for (int k = 0; k < blue_connect[point].size(); k++) {
                    tmp_point = blue_connect[point][k];
                    if (visited[tmp_point][0] != 1)
                        q.push({tmp_point, len + 1, 0});
                }
            }
        }
    }
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>> &redEdges, vector<vector<int>> &blueEdges) {
        vector<vector<int>> red_connect(n); //red_connect[i]表示点的集合，存在从i出发直接到这些点红色有向边
        vector<vector<int>> blue_connect(n);
        for (auto &vec : redEdges) {
            red_connect[vec[0]].push_back(vec[1]);
        }
        for (auto &vec : blueEdges) {
            blue_connect[vec[0]].push_back(vec[1]);
        }
        vector<int> answer(n, -1);
        answer[0] = 0;
        queue<tuple<int, int, int>> q;
        q.push({0, 0, 0});
        q.push({0, 0, 1});
        bfs(q, red_connect, blue_connect, answer, n, 0);
        return answer;
    }
};