Problem Link - Free ticket
Problem Statement
Indian National Olympiad in Informatics 2014
Nikhil’s slogan has won the contest conducted by Drongo Airlines and he is entitled to a free ticket between any two destinations served by the airline. All cities served by Drongo Airlines can be reached from each other by some sequence of connecting flights. Nikhil is allowed to take as many connecting flights as needed, but he must take the cheapest route between his chosen destinations.
Each direct flight between two cities has a fixed price. All pairs of cities connected by direct flights have flights in both directions and the price is the same in either direction. The price for a sequence of connecting flights is the sum of the prices of the direct flights along the route.
Nikhil has information about the cost of each direct flight. He would like to maximize the value of his prize, so he would like to choose a pair of cities on the network for which the cost of the cheapest route is as high as possible.
For instance, suppose the network consists of four cities {1, 2, 3, 4}, connected as shown on the right.
In this case, Nikhil should choose to travel between 1 and 4, where the cheapest route has cost 19. You can check that for all other pairs of cities, the cheapest route has a smaller cost. For instance, notice that though the direct flight from 1 to 3 costs 24, there is a cheaper route of cost 12 from 1 to 2 to 3.
Approach
To solve the problem, we need to find the shortest paths between all pairs of cities. This is a classic problem that can be solved using the Floyd-Warshall algorithm, which is an algorithm for finding the shortest paths between all pairs of nodes in a graph. Initially, we treat the direct flights as the shortest paths. Then, we update these paths by checking if there is a shorter path between two cities through an intermediate city. We do this for all possible intermediate cities. Once we calculate the shortest paths for all pairs of cities, the next task is to identify the maximum of the minimum paths between any two cities. This will be the pair of cities that has the highest cost for the cheapest route.
The algorithm starts by initializing the cost between each pair of cities as the direct flight cost, or infinity if no direct flight exists. We then repeatedly update the matrix of shortest paths by considering each city as an intermediate node and checking if traveling through this city offers a shorter path between two cities. Finally, we find the largest value from the shortest paths matrix, which represents the highest possible cheapest route cost between two cities.
Time Complexity
The time complexity of the Floyd-Warshall algorithm is O(N^3), where N is the number of cities, because we have three nested loops that each run N times.
Space Complexity
The space complexity is O(N^2), where N is the number of cities, because we need a matrix of size N \times N to store the distances between all pairs of cities.