760. Cheapest Road Network
A mountain region has n villages numbered 0 to n - 1. Each entry [u, v, cost] of connections describes a road that could be paved between villages u and v in either direction for cost coins. Several candidate roads may join the same pair, and a road may even start and end in the same village.
The council wants every village to be reachable from every other village using only paved roads, and it wants to pay as little as possible. Return the minimum total cost of the roads to pave, or -1 if no choice of roads can connect all the villages. A single village needs no roads, so the answer for n = 1 is 0.
Example 1
- Input:
- n = 4connections = [[0,1,5],[1,2,3],[0,2,4],[2,3,7],[1,3,9]]
- Output:
- 14
- Explanation:
Take the roads costing 3 (1-2), 4 (0-2) and 7 (2-3); together they connect all four villages for 14, and the remaining roads would only form loops or cost more.
Example 2
- Input:
- n = 4, connections = [[0,1,2],[2,3,2]]
- Output:
- -1
- Explanation:
Villages 0-1 and 2-3 form two separate pairs with no road between them, so the whole region can never be connected: -1.
Example 3
- Input:
- n = 3, connections = [[0,1,6],[0,1,2],[1,2,1]]
- Output:
- 3
- Explanation:
Between villages 0 and 1 the cheaper of the two parallel roads (2) is used, plus the road 1-2 (1), for a total of 3.
Constraints
- 1 ≤ n ≤ 105
- 0 ≤ connections.length ≤ 2 * 105
- 0 ≤ u, v < n
- 0 ≤ cost ≤ 104
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 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(m log m)
- Space
- O(n + m)