1385. Parallel Courses III — Bitmask Scheduling

There are n courses numbered 1 to n, and relations[i] = [a, b] means course a must finish before course b begins. Course i takes time[i-1] months, and any number of courses may run at the same time once their prerequisites are complete. Return the minimum number of months needed to finish all courses.

Input: A JSON object {"n": <course count>, "relations": [[a, b], ...], "time": [<durations>]}.

Output: Return the minimum total months to complete every course.

Examples

Input: {"n":3,"relations":[[1,3],[2,3]],"time":[3,2,5]}
Output: 8
Explanation: Course 3 waits for course 1 and finishes at month 8.

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 chain determines a total of 12 months.

Constraints

• 1 <= n <= 5 * 10^4
• 0 <= len(relations) <= 5 * 10^4
• 1 <= time[i] <= 10^4
• the prerequisite graph is acyclic

Asked by