leetcode

0 class Solution {

1 typedef vector<vector<int>> ADJ;

2

3 public:

4 vector<int> shortestAlternatingPaths(int n, vector<vector<int>> &redEdges,

5 vector<vector<int>> &blueEdges) {

6 vector<vector<int>> dist(2, vector<int>(n, INT_MAX));

7 vector<ADJ> adj(2, ADJ(n));

8 queue<pair<int, int>> q;

9

10 for (auto &e : redEdges)

11 adj[0][e[0]].push_back(e[1]);

12 for (auto &e : blueEdges)

13 adj[1][e[0]].push_back(e[1]);

14

15 q.push({0, 0});

16 q.push({0, 1});

17 dist[0][0] = dist[1][0] = 0;

18 while (!q.empty()) {

19 auto [crnt, col] = q.front();

20 q.pop();

21 for (int c : adj[!col][crnt]) {

22 if (dist[!col][c] != INT_MAX) continue;

23 dist[!col][c] = dist[col][crnt] + 1;

24 q.push({c, !col});

25 }

26 }

27

28 vector<int> res(n);

29 for (int i = 0; i < n; i++) {

30 res[i] = min(dist[0][i], dist[1][i]);

31 if (res[i] == INT_MAX) res[i] = -1;

32 }

33

34 return res;

35 }

36 };