leetcode

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