1
# Runtime: 1787 ms (Top 90.42%) | Memory: 42.7 MB (Top 96.74%)
2
class Solution:
3
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
4
        in_degree = defaultdict(int)
5
        graph = defaultdict(list)
6
        latest = [0] * (n + 1)
7
        for u, v in relations:
8
            graph[u].append(v)
9
            in_degree[v] += 1
10
        q = []
11
        for i in range(1, n + 1):
12
            if in_degree[i] == 0:
13
                latest[i] = time[i - 1]
14
                q.append(i)
15
        while q:
16
            node = q.pop()
17
            t0 = latest[node]
18
            for nei in graph[node]:
19
                t = time[nei - 1]
20
                latest[nei] = max(latest[nei], t0 + t)
21
                in_degree[nei] -= 1
22
                if in_degree[nei] == 0:
23
                    q.append(nei)
24
        return max(latest)