DSAhardGraphs~35m

The Architect

Problem

You are the lead dungeon architect at a game studio. Your procedural generation system has placed n rooms randomly across the map. You need to connect all rooms with corridors so players can explore every room — but carving corridors through rock is expensive.

Given n rooms numbered 0 to n-1 and a list of possible corridors [u, v, cost] representing the construction cost to connect rooms u and v, find the minimum total construction cost to connect all rooms. Corridors are undirected.

If it is impossible to connect all rooms (disconnected map), return -1.

Examples

Example 1

Input: (4, [[0,1,1],[1,2,1],[0,2,1],[2,3,10]])

Output: 12

Take corridors (0,1) cost 1, (1,2) cost 1 — adding (0,2) would create a cycle. Must add (2,3) cost 10 to reach room 3. Total: 12.

Example 2

Input: (4, [[0,1,5],[2,3,5]])

Output: -1

Rooms 0-1 and rooms 2-3 are separate islands with no corridor between them. Impossible to connect all rooms.

Example 3

Input: (3, [[0,1,1],[1,2,100],[0,2,2]])

Output: 3

Take (0,1) cost 1 and (0,2) cost 2 = total 3. Skip the expensive (1,2) cost 100 corridor.

Constraints

›1 <= n <= 1000
›0 <= len(corridors) <= 10000
›1 <= cost <= 10^6
›Corridors are undirected
›No self-loops

Loading question…