Description Link to heading
1129.shortest-path-with-alternating-colors
Solution Link to heading
First, we need represent the graph as an edge matrix, and we use bfs to find the shortest path.
In this problem, since the edge color of the shortest path must change along the path, when we judge whether the current node is visited, we should distinguish the cases that the current node is visited by red edges and the cases that the current node is visited by blue edges.
The element in the queue is tie(point, len, c_flag), which means the index of the current node, the length of the path to the current node(may not be the shortest), the color of the edge by which we visited the node(0 means blue and 1 means red).
The result of
q.push(0, 0, 0);
q.push(0, 0, 1);
bfs(q, red_connect, blue_connect, answer, n);
is the same as
q.push(0, 0, 0);
bfs(q, red_connect, blue_connect, answer, n);
q.pop();
q.push(0, 0, 1);
bfs(q, red_connect, blue_connect, answer, n);
Code Link to heading
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] == 1 means edge to be red, visited[k][0] == 1 means to be blue, both means the node has been visited.
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);
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;
}
};