1079. Second-Best Network
A company has n offices numbered 0 to n-1 and a list of possible cables: edges[i] = [u, v, cost] is a two-way cable between offices u and v. There may be several cables between the same pair of offices, and a cable from an office to itself is useless.
A network is a choice of exactly n-1 cables that connects all offices. The cheapest possible network has some total cost C. Management wants a backup plan: return the total cost of the cheapest network whose cost is strictly greater than C.
Return -1 if the offices cannot be connected at all, or if every possible network costs the same.
Example 1
- Input:
- n = 4, edges = [[0,1,1],[1,2,2],[2,3,3],[0,3,10]]
- Output:
- 13
- Explanation:
The cheapest network uses costs 1, 2, 3 (total 6). Adding the cost-10 cable and removing the cost-3 cable on its loop gives 13, the best strictly larger total.
Example 2
- Input:
- n = 3, edges = [[0,1,5],[1,2,5],[0,2,5]]
- Output:
- -1
- Explanation:
Every network uses two cables of cost 5 and costs 10, so no strictly more expensive network exists.
Example 3
- Input:
- n = 4, edges = [[0,1,2],[1,2,4],[0,2,4],[2,3,6],[1,3,9]]
- Output:
- 14
- Explanation:
The cheapest total is 2+4+6 = 12. Swapping the cost-2 cable for the spare cost-4 cable raises it to 14, which beats the other swap that reaches 15.
Constraints
1 ≤ n ≤ 104
0 ≤ edges.length ≤ 3 * 104
edges[i].length == 3
0 ≤ edges[i][0], edges[i][1] < n
1 ≤ edges[i][2] ≤ 109
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((n + m) log n)
- Space
- O(n log n)