2050. Parallel Courses III

Practice Parallel Courses III for free on NudgeCode: Hard, Graph pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

There are n courses labelled 1 .. n. Each relations[j] = [prev, next] means course prev must be finished before course next starts. Course i takes time[i-1] months. Any number of courses can be taken at the same time, and a course can start as soon as all its prerequisites are finished.

Return the minimum number of months needed to finish all courses. The prerequisite graph has no cycles.

Example

n = 3, relations = [[1,3],[2,3]], time = [3,2,5]  ->  8
n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]  ->  12

Constraints

• 1 <= n <= 5 * 10^4
• 0 <= relations.length <= 5 * 10^4; all pairs distinct
• 1 <= time[i] <= 10^4