← 返回 netflix 的题目列表Minimum Time to Finish All Dependent Tasks with Durations (Detect Cycles)
类型：online_judge
Problem: Minimum Time to Finish All Dependent Tasks with Durations (Cycle Detection Required)
You are given n tasks labeled 1..n. Each task i takes time[i] (a positive integer) to complete.
You are also given a list of dependencies dependencies, where each pair (u, v) means task u must be completed before task v can start.
A task may start as soon as all its prerequisites are completed. Parallel execution is allowed: any number of tasks can run simultaneously as long as their dependencies are satisfied.
Compute the minimum total time required to finish all tasks.
If the dependency graph contains a cycle such that it is impossible to finish all tasks, return -1.
Input format (suggested, for self-testing)
Line 1: two integers n m — number of tasks and number of dependencies.
Line 2: n integers — time[1..n].
Next m lines: each contains two integers u v representing an edge u -> v.
Output format
Print one integer: the minimum total completion time; if a cycle exists, print -1.
Constraints (suggested)
1 <= n <= 2 * 10^5
0 <= m <= 2 * 10^5
1 <= time[i] <= 10^9
Sample tests (5)
Test 1 Input:
3 2
3 2 5
1 3
2 3
Output:
8
Test 2 Input:
4 3
2 3 1 4
1 2
1 3
3 4
Output:
7
Test 3 (no dependencies, fully parallel) Input:
5 0
2 1 3 2 4
Output:
4
Test 4 (single chain) Input:
4 3
2 3 1 4
1 2
2 3
3 4
Output:
10
Test 5 (cycle exists) Input:
3 3
1 2 3
1 2
2 3
3 1
Output:
-1
Example
Input
3 2
3 2 5
1 3
2 3
Output
8