ORIGINAL CODING QUESTION
Minimum network wiring cost
Edges are undirected. Return the cheapest total edge cost connecting all vertices, or -1 if impossible. A one-vertex network costs zero.
Original exercise · hard. Editorial role relevance does not imply a company has asked this question.
Input and output
n m, then m triples (u,v,nonnegative cost).
Constraints
1 ≤ n ≤ 30; 0 ≤ m ≤ 100; vertex IDs in [0,n). 0 ≤ cost ≤ 100.
Example 1
Input
3 3 0 1 5 1 2 2 0 2 10
Output
7
Edges costing 5 and 2 connect all nodes for 7.
Example 2
Input
3 1 0 1 2
Output
-1
Vertex 2 cannot be connected.
Explain your approach
Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?
Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.
Hint 1
Consider candidate edges in ascending cost order.
Hint 2
Skip an edge that would close a selected cycle.
Hint 3
A connected spanning tree uses n-1 edges.
Practice this question
Save your work privately, explain decisions and return to your revision queue.
Open practice workspaceBrowse the question library →