1135. Connecting Cities With Minimum Cost
https://leetcode.com/problems/connecting-cities-with-minimum-cost
Description
There are n
cities labeled from 1
to n
. You are given the integer n
and an array connections
where connections[i] = [xi, yi, costi]
indicates that the cost of connecting city xi
and city yi
(bidirectional connection) is costi
.
Return the minimum cost to connect all the n
cities such that there is at least one path between each pair of cities. If it is impossible to connect all the n
cities, return -1
,
The cost is the sum of the connections' costs used.
Example 1:

**Input:** n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
**Output:** 6
**Explanation:** Choosing any 2 edges will connect all cities so we choose the minimum 2.
Example 2:

**Input:** n = 4, connections = [[1,2,3],[3,4,4]]
**Output:** -1
**Explanation:** There is no way to connect all cities even if all edges are used.
Constraints:
1 <= n <= 104
1 <= connections.length <= 104
connections[i].length == 3
1 <= xi, yi <= n
xi != yi
0 <= costi <= 105
ac
Last updated
Was this helpful?