leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1129.cpp (1097B)

      1 class Solution {
      2     typedef vector<vector<int>> ADJ;
      3 
      4   public:
      5     vector<int> shortestAlternatingPaths(int n, vector<vector<int>> &redEdges,
      6                                          vector<vector<int>> &blueEdges) {
      7         vector<vector<int>> dist(2, vector<int>(n, INT_MAX));
      8         vector<ADJ> adj(2, ADJ(n));
      9         queue<pair<int, int>> q;
     10 
     11         for (auto &e : redEdges)
     12             adj[0][e[0]].push_back(e[1]);
     13         for (auto &e : blueEdges)
     14             adj[1][e[0]].push_back(e[1]);
     15 
     16         q.push({0, 0});
     17         q.push({0, 1});
     18         dist[0][0] = dist[1][0] = 0;
     19         while (!q.empty()) {
     20             auto [crnt, col] = q.front();
     21             q.pop();
     22             for (int c : adj[!col][crnt]) {
     23                 if (dist[!col][c] != INT_MAX) continue;
     24                 dist[!col][c] = dist[col][crnt] + 1;
     25                 q.push({c, !col});
     26             }
     27         }
     28 
     29         vector<int> res(n);
     30         for (int i = 0; i < n; i++) {
     31             res[i] = min(dist[0][i], dist[1][i]);
     32             if (res[i] == INT_MAX) res[i] = -1;
     33         }
     34 
     35         return res;
     36     }
     37 };