Connecting Cities With Minimum Cost

Given n cities and a list of possible bidirectional roads with construction costs, build a network so that every city is reachable from every other city. Return the minimum total cost, or -1 if the cities cannot all be connected. Pattern focus: MST. Choose the lightest set of roads that connects the graph without cycles.

Input Format

n = number of cities, connections = bidirectional roads [city1, city2, cost]

Output Format

minimum cost to connect all cities, or -1 if impossible

Constraints

  • 1 <= n <= 10^5
  • 1 <= connections.length <= 2 * 10^5
  • 1 <= city1, city2 <= n
  • 1 <= cost <= 10^9

Examples

Example 1:

Input:

n = 3
connections = [[1,2,5],[1,3,6],[2,3,1]]

Output:

6

Explanation:

Choose roads (2,3) and (1,2) for total cost 6.

Example 2:

Input:

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

Output:

12

Explanation:

The minimum spanning tree uses the three cheaper roads with total cost 12.

Example 3:

Input:

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

Output:

-1

Explanation:

City 4 cannot be reached, so the network cannot be fully connected.

Loading...
Connecting Cities With Minimum Cost