leetcode

Solution to some Leetcode problems written in C++

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

2050.cpp (854B)

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