Second Best Minimum Spanning Tree

Given a connected weighted undirected graph, find the cost of the second-best minimum spanning tree. The second-best MST is the spanning tree with the smallest cost strictly larger than the best MST cost. Pattern focus: Minimum Spanning Tree. Compare each non-MST edge against the maximum-weight edge on the path it would replace.

Input Format

n = number of vertices, edges = weighted undirected edges [u, v, w]

Output Format

cost of the second-best spanning tree, or -1 if it does not exist

Constraints

  • 1 <= n <= 2000
  • 1 <= edges.length <= 2 * 10^4
  • 1 <= w <= 10^9

Examples

Example 1:

Input:

n = 4
edges = [[1,2,1],[2,3,2],[3,4,3],[1,4,10],[1,3,4],[2,4,5]]

Output:

8

Explanation:

The best MST costs 6, and the next cheapest distinct spanning tree costs 8.

Example 2:

Input:

n = 4
edges = [[1,2,1],[2,3,1],[3,4,1],[1,4,1],[1,3,2]]

Output:

4

Explanation:

The best MST has cost 3, and the second-best distinct one has cost 4.

Example 3:

Input:

n = 3
edges = [[1,2,5],[2,3,6],[1,3,20]]

Output:

25

Explanation:

The only MST costs 11, and the second-best tree costs 25.

Loading...
Second Best Minimum Spanning Tree