Sphere Online Judge

SPOJ Problem Set (classical)

15. The Shortest Path

Problem code: SHPATH


You are given a list of cities. Each direct connection between two cities has its transportation cost (an integer bigger than 0). The goal is to find the paths of minimum cost between pairs of cities. Assume that the cost of each path (which is the sum of costs of all direct connections belongning to this path) is at most 200000. The name of a city is a string containing characters a,...,z and is at most 10 characters long.

Input

s [the number of tests <= 10]
n [the number of cities <= 10000]
NAME [city name]
p [the number of neighbours of city NAME]
nr cost [nr - index of a city connected to NAME (the index of the first city is 1)]
           [cost - the transportation cost]
r [the number of paths to find <= 100]
NAME1 NAME2 [NAME1 - source, NAME2 - destination]
[empty line separating the tests]

Output

cost [the minimum transportation cost from city NAME1 to city NAME2 (one per line)]

Example

Input:
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

Output:
3
2

Warning: large Input/Output data, be careful with certain languages
Added by:Darek Dereniowski
Date:2004-05-10
Time limit:5s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: NODEJS PERL 6
Resource: DASM Programming League 2003 (problemset 11)

hide comments
2014-04-18 14:19:48 Gigi
hmm... what is the fast way to get unknown size strings from input?
2014-03-03 08:06:04 Nilesh Hamane
Dijkstra with Set - 7.73 and with priority queue - 2.91.
Huge difference because of find and erase in Set.
2014-01-20 14:52:28 umang gupta
what do the lines after the name of a city tell
2013-12-01 23:27:35 B Soma Naik
my programme works correctly for given cases.But i am getting run time error.Some more test cases appreciated.


Last edit: 2013-12-01 23:28:21
2013-11-01 09:21:54 Quantum
Finally done...:)
2013-10-26 16:33:59 [deleted]
Dijkstra + Binary Heap + Heap Sort + Binary Search = Fast algorithm
2013-08-25 14:13:00 Chinmay Kousik
This could be easily done with Floyd-Warshall, but sadly, memory constraints...
Djikstra is probably the best in this case, but I can't understand why we should use a priority queue over a standard queue...
@Chinmay Kousik if you use a priority queue, the algorithm will always pop the best path, reducing the complexity. With a standard queue you will check, in the worst case, all the possible paths from a node.

Last edit: 2014-03-16 21:53:47
2013-08-12 10:29:59 Ouditchya Sinha
@sanket sudake : Clearly the constraints make it impossible to be solved by Floyd - Warshall as we'll need a 2-D array of size 10000 X 10000 which will give runtime error. I agree with Erti-Chris Eelmaa.
2013-07-20 07:07:18 Erti-Chris Eelmaa
Simple Dijkstra+priority_QUEUE+few optimizations. If you still can't pass, use fastIO.
2013-07-19 15:32:32 [bLanK]
huhh...after lots of tle's......finaly AC....
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.