Which Way Do I Go?
Time Limit: 1 Second Memory Limit: 32768 KB
You've decided that the time is right for the next Internet map startup. Your inspiration for this venture is your directionally impaired spouse, who doesn't care for the shortest or quickest routes generated by current online map systems-instead, easier is better.The backbone of your operation is, of course, your algorithm for calculating directions. Your algorithm must accept the map from your massive database of the entire country and produce the best route that meets the customer's query. Queries consist of an origin, destination, and the optimization goal, which can be for the shortest route, fastest route, or route with the fewest turns. You are guaranteed that there will be a path between source and destination for any query asked.
Input
There are three sections for each test case in the input file, the first lists the cities, the second lists the roads, and the third lists the queries.
The first line of input is the number of cities, c, followed by c lines each containing the name of a city. There is no whitespace in a city name.
The next line is the number of roads, r, followed by r lines describing a road. Each road description has the following form:
There is no whitespace in a road's name. Roads may pass through any number of cities. The cities appear in the order the road passes through them. No road passes through the same city multiple times. Roads are bidirectional. The distance and time (both real numbers) it takes to follow a road between each pair of cities is the distance and time listed between those two names. When following a road between multiple cities (A to C, for example), the distance and time is cumulative for all steps along the path.
The next line is the number of queries, q, followed by q lines each containing one query. Queries are of the form:
Querytype is one of time, distance, or turns and the origin and destination are the names of cities.
The test cases end at end-of-file.
Output
For each query, your output will begin with a line:
from
Each following line will be of the form:
which lists the road to turn onto from the previous city, and the city to take that road to. If a single road is followed between multiple cities, only the final city reached on that road before turning onto another road is listed. The final city listed will be the destination city. If there are several rounds to choose at a spot, use the one that appears earlier on the input list.
Separately subsequent test cases with a single blank line.
Sample Input
5 Chicago DesMoines OklahomaCity Dallas LosAngeles 4 I80 Chicago 300 4 DesMoines I35 DesMoines 550 7.3 OklahomaCity 205 3 Dallas I40 OklahomaCity 1330 20.5 LosAngeles Rt66 Chicago 2448 46 LosAngeles 2 time Chicago LosAngeles turns Chicago LosAngeles
Sample Output
from Chicago I80 to DesMoines I35 to OklahomaCity I40 to LosAngeles from Chicago Rt66 to LosAngelesSubmit
Source: Mid-Atlantic USA 2003