FunctionRacerProblemsRace

Connect All Offices

MediumGraphsPython, JavaScript, TypeScript, Java, C++

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

n 4
cables [[0,1,1],[1,2,2],[2,3,3],[0,3,10],[0,2,4]]
returns 6

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

n 3
cables [[0,1,5]]
returns -1

Office 2 has no cable on offer at all.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems