Connect All Villages With the Least Cable
Solve this ProblemA 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.
Test Case 1:
Test Case 2:
Test Case 3:
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
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Set of n − 1 Cables
BruteA cheapest connection uses exactly n − 1 cables (any more would add a cycle and waste money). List all possible cables, then try every choice of n − 1 of them: use a component label per village, merge the two labels of every chosen cable, and check that in the end all villages share one label. Keep the smallest total cost among the choices that connect everything. The number of choices grows very quickly with the number of cables.
O(C(E, n−1) · n²)O(E)1class Solution {
2 public int cheapestNetwork(int[][] weights) {
3 int n = weights.length;
4 List<int[]> edges = new ArrayList<>();
5 for (int u = 0; u < n; u++) {
6 for (int v = u + 1; v < n; v++) {
7 if (weights[u][v] > 0) edges.add(new int[]{u, v, weights[u][v]});
8 }
9 }
10 int E = edges.size();
11 int best = Integer.MAX_VALUE;
12 for (int mask = 0; mask < (1 << E); mask++) {
13 if (Integer.bitCount(mask) != n - 1) continue;
14 int[] comp = new int[n];
15 for (int i = 0; i < n; i++) comp[i] = i;
16 int total = 0;
17 for (int e = 0; e < E; e++) {
18 if ((mask & (1 << e)) == 0) continue;
19 int[] edge = edges.get(e);
20 int from = comp[edge[1]], to = comp[edge[0]];
21 for (int i = 0; i < n; i++) {
22 if (comp[i] == from) comp[i] = to;
23 }
24 total += edge[2];
25 }
26 boolean connected = true;
27 for (int i = 0; i < n; i++) {
28 if (comp[i] != comp[0]) connected = false;
29 }
30 if (connected) best = Math.min(best, total);
31 }
32 return best == Integer.MAX_VALUE ? -1 : best;
33 }
34}Optimal — Prim’s Algorithm
OptimalGrow the network from village 0. Keep, for every village not yet connected, the cost of the cheapest cable that links it to the connected part (key). Repeatedly connect the village with the smallest key: add that cost to the total, and update the keys of its neighbours when the cable from the newly connected village is cheaper. If the smallest key is still infinity, the remaining villages cannot be reached and the answer is -1. Choosing the cheapest cable that leaves the connected part is always safe (the cut property). A linear scan per round gives O(n²); a heap gives O(E log n).
O(n²)O(n)1class Solution {
2 public int cheapestNetwork(int[][] weights) {
3 int n = weights.length;
4 int INF = Integer.MAX_VALUE;
5 boolean[] inTree = new boolean[n];
6 int[] key = new int[n];
7 Arrays.fill(key, INF);
8 key[0] = 0;
9 int total = 0;
10 for (int round = 0; round < n; round++) {
11 int u = -1;
12 for (int i = 0; i < n; i++) {
13 if (!inTree[i] && (u == -1 || key[i] < key[u])) u = i;
14 }
15 if (key[u] == INF) return -1;
16 inTree[u] = true;
17 total += key[u];
18 for (int v = 0; v < n; v++) {
19 if (weights[u][v] > 0 && !inTree[v] && weights[u][v] < key[v]) {
20 key[v] = weights[u][v];
21 }
22 }
23 }
24 return total;
25 }
26}