4353: Multimodal Transport

New methods of shipping goods have transformed the transportation industry and helped usher in an era of global commerce.  Nowadays, someone can click a few buttons and have an item leave a factory on the other side of the world and show up at their doorstep the next day.  To help accomplish this, there are a number of modes of transport within the shipping industry.  The four most common are: air, boat, rail and truck.   
 
Transportation companies tend to keep the mode of transport consistent throughout a packages journey (route/path).  However, when customers are not very time sensitive, often times the cheapest way to move a package from one location to another is to use more than one mode of transport.  One has to be careful, though, as additional costs are incurred when switching between transport modes within a city on the package path.   (Switching transport mode refers to a package leaving a city in a different mode than it arrived at the city, e.g., the package arrived by air and leaves by truck.) 
 
A new startup, KnightShip, has asked for your help in figuring out the cheapest way to ship packages when switching between transportation modes is acceptable.   The Problem:   Given the costs for various modes of transport between cities, and the cost of switching mode within a city, calculate the lowest cost to transport an item from an origin to a destination.   

The first input line contains a positive integer, n, indicating the number of test cases to process.  Each test case will contain multiple input lines.  The first line of each test case will contain an integer, c (2 ≤ c ≤ 400), representing the number of cities within the transportation network. 
 Each of the following c input lines contains two values: a string (1 to 20 uppercase letters, inclusive), representing the name of a city and an integer (between 1 and 1000, inclusive), representing the cost of changing the transport mode within that city. 
 
The city information for a test case is followed by the route information for the test case.  There will be an input line containing one integer, r (1 ≤ r ≤ 40000), representing the number of route segments in the network.  This will be followed by a listing of all route segments, one per line.  Each route segment will contain four values: p, q, representing two cities from the previous list, m, representing the transport mode (one of four values AIR, BOAT, RAIL, TRUCK) for that route segment, and an integer v (1 ≤ v ≤ 1000), representing the cost to ship a package between the two cities (either direction).  Note that there may be no route segments for a particular transport mode.  There will be no duplicate city pair within a given mode of transport, but different transport modes (even all four modes) can exist between the same two cities.   The last input line for a test case contains two distinct cities o and d which represent the origin and destination cities for which we want the minimum cost to ship a package.  Cities o and d are guaranteed to have a path (of finite cost) that exists between them.  Any mode of transport can be used to leave city o and any mode can be used to reach city d (they don’t necessarily need to match).  The transport mode can change in the intermediate stages as well.
    

For each test case, output a single integer on a line by itself indicating the minimum cost to move a package from city o to city d.

2
4
ORLANDO 10
TAMPA 15 
MIAMI 5 
JACKSONVILLE 10 
7
TAMPA JACKSONVILLE AIR 100
MIAMI TAMPA SEA 70
JACKSONVILLE MIAMI RAIL 45
ORLANDO JACKSONVILLE TRUCK 85
TAMPA ORLANDO RAIL 10
MIAMI JACKSONVILLE SEA 15
ORLANDO MIAMI TRUCK 15
JACKSONVILLE TAMPA
2
ORLANDO 15
TAMPA 10
3
ORLANDO TAMPA AIR 7
TAMPA ORLANDO TRUCK 3
ORLANDO TAMPA RAIL 19
ORLANDO TAMPA 

55
3

Due to the large input bounds on the number of cities (2 ≤ c ≤ 400) and route segments r (1 ≤ r ≤ 40000), an Order-cubed solution will result in “time limit exceeded” with the given judge run time for this problem.