问题描述
解题思路
首先，将本题的图结构以边表的形式表现出来，然后采取广度优先搜索的方式寻找最短路径，一般来说广度优先搜索能够保证找到的是最短路径。
在本题中，由于要求最短路径是交替出现的，那么在判断节点是否已经访问过时，要分红色路径访问节点和蓝色路径访问节点两种情况讨论。
队列中的元素为三元组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;
}
};