We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
If the cost of a road is >= the cost of a library, just build a library at each node.
Otherwise, use DFS to get the number of nodes (ct) in each connected component. Put 1 library in each component, and the total per component cost is simply ct-1 (a road to connect to each node in the compomnent) * cost of a road + cost of one library.
You'll never put more than one library per component because once you're adding an additional node to a component, the cost of just building a road will always be cheaper than the cost of disconnecting the node (not building a road) and building a library instead.
Roads and Libraries
You are viewing a single comment's thread. Return to all comments →
It's easy to overthink this one.
If the cost of a road is >= the cost of a library, just build a library at each node.
Otherwise, use DFS to get the number of nodes (ct) in each connected component. Put 1 library in each component, and the total per component cost is simply ct-1 (a road to connect to each node in the compomnent) * cost of a road + cost of one library.
You'll never put more than one library per component because once you're adding an additional node to a component, the cost of just building a road will always be cheaper than the cost of disconnecting the node (not building a road) and building a library instead.