Asked at

Connecting Cities With Minimum Cost

Medium
VerifiedMSTUnion FindGreedy~25 min

You have n cities labeled 1..n and a list of weighted connections, each [city1, city2, cost] joining two cities at the given cost.

Return the minimum total cost to connect every city, or -1 if connecting them all is impossible.

The input arrives as a single object { n, connections }.

Examples

in{ n: 3, connections: [[1,2,5],[1,3,6],[2,3,1]] }
out6

Pick edges (2,3,1) and (1,2,5) to connect all three cities.

in{ n: 4, connections: [[1,2,3],[3,4,4]] }
out-1

Cities 1-2 and 3-4 stay in separate groups, so return -1.

Constraints

  • 1 ≤ n ≤ 10⁴
  • 1 ≤ connections.length ≤ 10⁴
  • connections[i] = [city1, city2, cost], cities labeled 1..n
  • 1 ≤ cost ≤ 10⁵

Get help

🔑

Sign in to solve

Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.