leetcode

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

2050.cpp (854B)

      1 class Solution {
      2   public:
      3     int minimumTime(int n, const vector<vector<int>> &relations, const vector<int> &time) {
      4         vector<vector<int>> adj(n);
      5         vector<int> count(n, 0), wait(n, 0);
      6 
      7         for (const auto &relation : relations) {
      8             adj[relation[0] - 1].push_back(relation[1] - 1);
      9             count[relation[1] - 1]++;
     10         }
     11 
     12         queue<int> q;
     13         int res = 0;
     14         for (int i = 0; i < n; i++)
     15             if (!count[i]) q.push(i);
     16         while (!q.empty()) {
     17             const int root = q.front();
     18             wait[root] += time[root];
     19             res = max(res, wait[root]);
     20             q.pop();
     21             for (const int next : adj[root]) {
     22                 wait[next] = max(wait[next], wait[root]);
     23                 if (!--count[next]) q.push(next);
     24             }
     25         }
     26 
     27         return res;
     28     }
     29 };