Ashoke, a young budding Travel Entrepeneur, is quite saddened after incurring loss from past several trips.
He gets an offer from one of the travel agencies to carry out a trip. Ashoke is lit! This is his first venture towards making a profit.
Travel agency provides Ashoke the distances between every pair of locations he needs to cover. He can start and end at any two (different) locations he wants, but he must make sure that he takes travellers to visit each location exactly once.
Now, help Ashoke to maximize his profits by suggesting him the shortest distance he can travel to achieve this?
For example, given the following distances:
Bangalore to Hubli
= 464
Bangalore to Dharwad
= 518
Hubli to Dharwad
= 141
The possible routes are:
Hubli -> Bangalore -> Dharwad = 982
Bangalore -> Hubli -> Dharwad = 605
Bangalore -> Dharwad -> Hubli = 659
Hubli -> Dharwad -> Bangalore = 659
Dharwad -> Hubli -> Bangalore = 605
Dharwad -> Bangalore -> Hubli = 982
The shortest path here is Bangalore -> Hubli -> Dharwad = 605
, so the answer is 605
for this example.
Help Ashoke! Find the input file in the repository.