Parallel Courses III

Given n courses, prerequisite relations, and the time required for each course, return the minimum time needed to finish all courses. Pattern focus: DAG. This is a longest-path-on-DAG problem where course durations accumulate along dependency chains.

Input Format

n = number of courses, relations = prerequisite edges, time = duration for each course

Output Format

minimum total time to finish all courses

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • n, relations, time must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

n = 3
relations = [[1,3],[2,3]]
time = [3,2,5]

Output:

8

Explanation:

Courses 1 and 2 can run in parallel before course 3.

Example 2:

Input:

n = 5
relations = [[1,5],[2,5],[3,5],[3,4],[4,5]]
time = [1,2,3,4,5]

Output:

12

Explanation:

The critical path determines the total time.

Loading...
Parallel Courses III - Graph Fundamentals