1
class Solution {
2
 public:
3
  int minimumTime(int n, vector<vector<int>> &relations, vector<int> &time) {
4
    vector<vector<int>> adjList(n);
5
    vector<int> inDegree(n), cTime(n, 0);
6

7
    for (auto &r : relations) { // Create adjacency list and in degree count vectors.
8
      adjList[r[0] - 1].push_back(r[1] - 1);
9
      inDegree[r[1] - 1]++;
10
    }
11
    queue<pair<int, int>> q;
12

13
    for (int i = 0; i < n; i++) // Get all nodes with in-degree=0 and store add them to the queue.
14
      if (!inDegree[i]) q.push({i, 0});
15

16
    while (!q.empty()) {
17
      auto [node, t] = q.front(); // Process node `node`.
18
      q.pop();
19

20
      // Completion time of the current node the time when the processing
21
      // started `t` (Max time at which prerequisutes completed) + the time
22
      // taken to process it `time[node]`.
23
      int completionTime = t + time[node];
24
      cTime[node] = completionTime; // Store the final completion time of the node `node`.
25

26
      for (int &n : adjList[node]) {
27
        // Update the intermediate completion time of the child node `n`.
28
        // This means that node `n` would start processing at least at
29
        // `cTime[n]`.
30
        cTime[n] = max(cTime[n], completionTime);
31

32
        if (!--inDegree[n]) // Add the node with in-degree=0 to the queue.
33
          q.push({n, cTime[n]});
34
      }
35
    }
36
    // Return the maximum time it took for a node/course to complete as our
37
    // result.
38
    return *max_element(cTime.begin(), cTime.end());
39
  }
40
};