Problem statement

https://leetcode.com/problems/parallel-courses-iii/

Solution

The idea is that what we actually need to find is the longest node weighted path, that is if we start with some node and move only by allowed arrows, what is the maximum sum we can get when we sum all values in visited nodes. For this purpuse we can use dynamic programming. Let dp(node) be the longest path when we reached node. Then we need to check from what nodes we can arrive and take the maximum one.

Complexity

Time complexity is O(E + n), where E is number of edges. Space complexity is O(E + n) as well to keep graph G and for dp cache.

Code

class Solution:
    def minimumTime(self, n, R, T):
        G = defaultdict(list)
        for x, y in R:
            G[y].append(x)

        @lru_cache(None)
        def dp(node):
            return T[node - 1] + max([dp(child) for child in G[node]] + [0])

        return max(dp(i) for i in range(1, n+1))

Code 2

We can write it in shorher way

class Solution:
    def minimumTime(self, n, R, T):
        G = defaultdict(list)
        for x, y in R: G[y] += [x]
        dp = cache(lambda x:T[x - 1] + max([dp(c) for c in G[x]] + [0]))
        return max(dp(i+1) for i in range(n))