101
0/320
Loading content...
A developing community consists of n residential buildings, numbered from 1 to n. Your task is to design an infrastructure plan to supply a critical utility (such as electricity, fiber internet, or clean water) to every building at the minimum total cost.
There are two ways to provide the utility to any building:
Local Installation: Each building can have its own independent utility source installed directly. The cost of installing a local source at building i is given by localCosts[i - 1] (note the 0-indexing adjustment).
Shared Connection: You can lay infrastructure (cables, pipes, or conduits) to connect buildings, allowing them to share a utility source. The array connections describes possible links, where each connections[j] = [building1, building2, cost] represents the expense of establishing a bidirectional link between building1 and building2. Multiple connection options may exist between the same pair of buildings with different costs.
The objective is to determine the minimum total cost required to ensure that every building in the community has access to the utility—either through a local installation or via a shared connection path to a building that has a local installation.
Key Insight: Think of this as a graph problem where buildings are nodes. Local installations can be modeled as edges connecting each building to a virtual "utility source" node, and shared connections are edges between buildings. The goal becomes finding the minimum cost to connect all buildings to at least one utility source—a classic minimum spanning tree variant.
n = 3
localCosts = [1,2,2]
connections = [[1,2,1],[2,3,1]]3The optimal strategy is to install a local source at building 1 (cost = 1), then connect building 2 to building 1 (cost = 1), and connect building 3 to building 2 (cost = 1). Total cost = 1 + 1 + 1 = 3. This is cheaper than installing local sources everywhere (1 + 2 + 2 = 5).
n = 2
localCosts = [1,1]
connections = [[1,2,1],[1,2,2]]2There are three equally optimal strategies, each costing 2: • Install local sources at both buildings (1 + 1 = 2) • Install at building 1, connect building 2 via the cheaper link (1 + 1 = 2) • Install at building 2, connect building 1 via the cheaper link (1 + 1 = 2) When multiple connections exist between the same buildings, always consider the cheapest option.
n = 4
localCosts = [5,10,10,10]
connections = [[1,2,1],[2,3,1],[3,4,1]]8Install a local source at building 1 (cost = 5), then connect all other buildings in a chain: 1→2 (cost = 1), 2→3 (cost = 1), 3→4 (cost = 1). Total cost = 5 + 1 + 1 + 1 = 8. This is much cheaper than installing local sources at all buildings (5 + 10 + 10 + 10 = 35).
Constraints