Problem Link - High Speed Network
Problem Statement
The Government of Siruseri is no different from any other when it comes to being “capital-centric” in its policies. Recently the government decided to set up a nationwide fiber-optic network to take Siruseri into the digital age. And as usual, this decision was implemented in a capital centric manner — from each city in the country, a fiber optic cable was laid to the capital! Thus, traffic between any two cities had to go through the capital.
Soon, it became apparent that this was not quite a clever idea, since any breakdown at the capital resulted in the disconnection of services between other cities. So, in the second phase, the government plans to connect a few more pairs of cities directly by fiber-optic cables. The government has specified that this is to be done in such a way that the disruption of services at any one city will still leave the rest of the country connected.
The government has data on the cost of laying fiber optic cables between every pair of cities. You task is to compute the minimum cost of additional cabling required to ensure the requirement described above is met.
Approach
The problem is a minimum spanning tree (MST) problem, where the goal is to connect all cities with the least cost while ensuring the network remains connected. The logic uses Prim's algorithm to find the MST. Start by initializing the cost to connect all cities to infinity, except for the first city. This ensures the algorithm starts from the first city and progressively includes other cities in the MST. Use a visited array to keep track of cities already included in the MST. In each iteration, find the unvisited city with the smallest connection cost and add it to the MST. Update the cost of connecting all remaining unvisited cities based on the current city. Repeat this process until all cities are connected. The final answer is the sum of all selected connection costs.
Time Complexity
The time complexity is O(n^2), where n is the number of cities, due to the nested loops for finding the minimum cost and updating distances.
Space Complexity
The space complexity is O(n^2), as the adjacency matrix stores the cost between every pair of cities.