1080. Network With a Must-Use Cable
A city plans to connect n depots numbered 0 to n-1. Each entry edges[i] = [u, v, cost] is a possible two-way cable between depots u and v. Cables may repeat between the same pair of depots, and a cable that starts and ends at the same depot is allowed in the list but connects nothing.
The array mustUse contains the distinct indices of one or more cables in edges that the contract forces the city to lay. Choose a set of exactly n-1 cables that contains all of them and connects every depot, and make its total cost as small as possible.
Return that minimum total cost, or -1 if no such set exists (for example because the forced cables already close a loop, or the depots cannot all be connected).
Example 1
- Input:
- n = 4edges = [[0,1,4],[1,2,6],[2,3,5],[0,3,10],[1,3,8]]mustUse = [3]
- Output:
- 19
- Explanation:
The forced cable 0-3 costs 10; adding the cheap cables 0-1 (4) and 2-3 (5) then connects all four depots for 19.
Example 2
- Input:
- n = 3, edges = [[0,1,2],[1,2,3],[0,2,4]], mustUse = [2]
- Output:
- 6
- Explanation:
The forced cable 0-2 costs 4 and the cheapest way to reach depot 1 is the cost-2 cable, giving 6.
Example 3
- Input:
- n = 3edges = [[0,1,2],[1,2,3],[0,2,4]]mustUse = [0,1,2]
- Output:
- -1
- Explanation:
All three forced cables together form a triangle, so they can never be part of a loop-free network: the answer is -1.
Constraints
1 ≤ n ≤ 5 * 104
0 ≤ edges.length ≤ 105
edges[i].length == 3
0 ≤ edges[i][0], edges[i][1] < n
1 ≤ edges[i][2] ≤ 1000
1 ≤ mustUse.length ≤ edges.length, all values distinct and valid indices into edges
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(m log m)
- Space
- O(n + m)