Laying cable to connect every village for the least money: always build the cheapest link that connects something new.
Clues that point here
→ Connect all points at minimum cost
→ Weighted undirected graph
→ No cycles in the result
Not this pattern when
✕ You need the shortest path between two specific nodes (Dijkstra)
The template
A skeleton to adapt. The parts in comments are what changes from problem to problem.
Minimum Spanning Tree · template
Arrays.sort(edges, (a, b) -> a[2] - b[2]); // {u, v, cost}
int total = 0, used = 0;
for (int[] e : edges) {
if (union(e[0], e[1])) { // union-find: joins two groups
total += e[2];
if (++used == n - 1) break;
}
}
return used == n - 1 ? total : -1;