Cheapest Wiring Plan
EasyAdvanced GraphsFree
Problem
A campus has n buildings numbered 0 to n - 1. A contractor quoted a list of possible fibre cables: cables[i] = [u, v, cost] would connect buildings u and v in both directions.
Choose a set of cables so that every building can reach every other one (directly or through other buildings) at the minimum total cost. Return that cost, or -1 if no choice of cables connects the whole campus.
Example 1
- Input:
- n = 4, cables = [[0,1,3],[1,2,1],[2,3,4],[0,3,2],[0,2,5]]
- Output:
- 6
Take 1–2 (1), 0–3 (2) and 0–1 (3). All four buildings are connected for 6.
Example 2
- Input:
- n = 3, cables = [[0,1,5]]
- Output:
- -1
Building 2 has no quoted cable.
Example 3
- Input:
- n = 1, cables = []
- Output:
- 0
Constraints
- 1 ≤ n ≤ 10^4
- 0 ≤ cables.length ≤ 10^5
- 1 ≤ cost ≤ 10^4
- u ≠ v; duplicates may appear.
Hint
Show the first hint
A cheapest connecting set never contains a cycle: you could drop the most expensive cable on it.
Walkthrough
How to approach it
01Clarify before coding
- Are cables bidirectional? Yes, so this is an undirected graph.
- What if the campus cannot be connected? Return -1.
- Is a single building already connected? Yes, the cost is 0.
02Brute force
Try every subset of n - 1 cables and keep the cheapest one that connects everything.
Cost: Exponential: C(E, n - 1) subsets, hopeless beyond a handful of cables.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.