2050. Parallel Courses III

• find the max for each node, and memorise them

class Solution(object):
    def minimumTime(self, n, relations, time):
        adj = collections.defaultdict(list)

        for prev, nxt in relations:
            adj[prev].append(nxt)

        
        max_paths = {}

        def dfs(src):
            if src in max_paths:
                return max_paths[src]

            max_ = time[src - 1]

            for node in adj[src]:
                max_ = max(max_, time[src - 1] + dfs(node))

            max_paths[src] = max_
            return max_

        for i in range(1, n + 1):
            dfs(i)

        return max(max_paths.values())