leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1129.cpp (1097B)

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 };