Connect All Villages With the Least Cable
Implement cheapestNetwork
A telecom company wants to connect n villages. Some pairs of villages can be joined by a cable with a given cost (a symmetric cost matrix, 0 means impossible). Find the smallest total cost of a set of cables that connects all villages to each other, or -1 if that cannot be done.
The cheapest connection is a minimum spanning tree. Prim's algorithm grows it from one village, always adding the cheapest cable that leaves the connected part.
Example 1:
Input: weights = [[0,4,3,0,0,0],[4,0,1,2,0,0],[3,1,0,4,0,0],[0,2,4,0,2,7],[0,0,0,2,0,6],[0,0,0,7,6,0]]
Output: 14
Example 2:
Input: weights = [[0,7],[7,0]]
Output: 7
Example 3:
Input: weights = [[0,0],[0,0]]
Output: -1
+ 14 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 6 villages numbered 0 … n-1; weights is a symmetric n × n matrix: weights[u][v] = 0 means a cable between u and v cannot be laid, and weights[u][v] = w (1 ≤ w ≤ 20) means it costs w - ●
weights[u][u] = 0 - ●
You choose some of the possible cables so that every village can reach every other village through the chosen cables - ●
Return the smallest possible total cost, or -1 if the villages cannot all be connected
weights =
[[0,4,3,0,0,0], [4,0,1,2,0,0], [3,1,0,4,0,0], [0,2,4,0,2,7], [0,0,0,2,0,6], [0,0,0,7,6,0]]