1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
// 1129. Shortest Path with Alternating Colors
#include "leetcode.h"
class Solution {
public:
vector<int> shortestAlternatingPaths(int n, vvd & redEdges,
vvd & blueEdges) {
vector<int> ans(n, -1), v1(n, 0), v2(n, 0);
vector<vector<pair<int, int>>> vvp(n);
queue<pair<int, int>> qp;
for (auto &it : redEdges)
vvp[it[0]].push_back({it[1], 1});
for (auto &it : blueEdges)
vvp[it[0]].push_back({it[1], 2});
ans[0] = 0, v1[0] = 1, v2[0] = 1;
int tmp = 1;
for (auto &it : vvp[0]) {
qp.push(it);
if (ans[it.first] == -1)
ans[it.first] = tmp;
}
while (!qp.empty()) {
int len = qp.size();
tmp++;
for (int i = 0; i < len; ++i) {
auto val = qp.front();
qp.pop();
if (val.second == 1)
v1[val.first] = 1;
else
v2[val.first] = 1;
for (auto &it : vvp[val.first]) {
if (val.second == 1 && (v2[it.first] || it.second == 1))
continue;
if (val.second == 2 && (v1[it.first] || it.second == 2))
continue;
qp.push(it);
if (ans[it.first] == -1)
ans[it.first] = tmp;
}
}
}
return ans;
}
};
int main() {
Solution obj;
vvd re1 = {{0, 1}, {1, 2}}, be1 = {};
vvd re2 = {{0, 1}}, be2 = {{2, 1}};
for (auto i : obj.shortestAlternatingPaths(3, re1, be1))
cout << i << ' '; // expect: 0 1 -1
cout << endl;
for (auto i : obj.shortestAlternatingPaths(3, re2, be2))
cout << i << ' '; // expect: 0 1 -1
}
|