15 (SHPATH) - The Shortest Path
We are given up to 10000 cities. For each city, we are given a list of transportation costs, specifying the cost of travelling from that city to another, given city. Then, we are given up to 100 queries, each of which asks us to determine the minimum possible cost of travelling between two given cities.
Let each city be a vertex, and each pair of connected cities be an edge whose weight is equal to the transportation cost. Then, the minimum possible cost for travelling between two given cities is the shortest path from one city to the other. Since all transportation costs are positive, we can use Dijkstra's algorithm to compute the length of the shortest path from one vertex to another. The only other thing is that the queries are names of cities. In order to find the vertex number for a particular city, we can binary search on a sorted list of names.
This problem requires a lot of optimization in order to get a solution which will run within the time limit. For this reason, the problem TSHPATH (http://spoj.pl/problems/TSHPATH) is provided for the sake of experimentation.
1 4 gdansk 2 2 1 3 3 bydgoszcz 3 1 1 3 1 4 4 torun 3 1 3 2 1 4 1 warszawa 2 2 4 3 1 2 gdansk warszawa bydgoszcz warszawa