1
class Solution {
2
  public int minimumTime(int n, int[][] relations, int[] time) {
3
    List<Integer> adj[] = new ArrayList[n];
4
    int indegree[] = new int[n];
5
    int completionTime[] = new int[n];
6
    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
7
    for (int relation[] : relations) {
8
      int u = relation[0] - 1, v = relation[1] - 1;
9
      adj[u].add(v);
10
      indegree[v]++;
11
    }
12
    Queue<Integer> q = new LinkedList<>();
13
    for (int i = 0; i < n; i++) {
14
      if (indegree[i] == 0) { // if no prerequisite add it to queue
15
        completionTime[i] = time[i];
16
        q.add(i);
17
      }
18
    }
19

20
    while (!q.isEmpty()) {
21
      int u = q.poll();
22
      for (int v : adj[u]) {
23
        completionTime[v] = Math.max(completionTime[v], completionTime[u] + time[v]);
24
        if (--indegree[v] == 0) { // when all prerequisite are complete add the next course
25
          q.add(v);
26
        }
27
      }
28
    }
29
    int res = 0;
30
    for (int x : completionTime) res = Math.max(res, x);
31
    return res;
32
  }
33
}