Connect All Offices
A company has n offices numbered 0 to n - 1. cables lists possible installations as entries [a, b, cost]: paying cost installs a cable between offices a and b that carries data both ways. The same pair may appear several times with different costs, and a != b.
Return the smallest total cost that lets every office exchange data with every other office, directly or through other offices. Return -1 if that cannot be achieved with the cables on offer. A single office needs no cable, so the answer is 0 when n == 1.
Example 1
Cables 0-1, 1-2 and 2-3 cost 1 + 2 + 3 = 6 and link all four offices; the cables costing 10 and 4 are not needed.
Example 2
Office 2 has no cable on offer at all.
Constraints
1 <= n <= 500 <= len(cables) <= 100cables[i] = [a, b, cost]with0 <= a, b < n,a != band1 <= cost <= 100
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Count the Shortest RoutesMedium
- Forced SidesMedium
- Largest PatchMedium
- Longest TrailMedium
- Lowest High PassMedium
- Mutual Reach GroupsMedium
- Nodes on a LoopMedium
- Rectangular IslandsMedium