aboutsummaryrefslogtreecommitdiff
path: root/shortest_path_alternate_color.cpp
blob: 5122fefd9caf5e977c73e42ca70141ed17ec762c (plain)
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(int) & redEdges,
                                       vvd(int) & 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(int) re1 = {{0, 1}, {1, 2}}, be1 = {};
  vvd(int) 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
}