Trip Routing

Interview

Time limit1sMemory limit128 MB

Summary

Given a bidirectional weighted map of city pairs, find and print the shortest route between each queried city pair with full leg-by-leg formatting.

Level: Medium6 of 10
Topics: Graph, Shortest path, Implementation, Simulation
Solved: No attempts yet

Problem

Your employer, the California Car Club (CCC), has decided to offer a trip-routing service to its members. Write a program that reads a list of (departure point, destination point) pairs and computes the shortest route between the two cities of each pair. For every trip, print a report that itemises each city the route passes through, together with the route names and the mileage of each leg.

Input

The input has two parts.

The first part is a map given as a list of highway segments. Each segment is one line of four comma-separated fields:

Fields 1 and 2: the names of the two cities at the ends of the segment (1–20 characters each).
Field 3: the route name (1–10 characters).
Field 4: the distance in miles between the two endpoints, a positive integer.

Every highway segment may be travelled in either direction. The list of segments is terminated by an empty line.

The second part is a list of (departure point, destination point) pairs, one per line, written as departure,destination. Every city named here also appears in the map, and a path always connects the two cities. This list runs to the end of the input.

Output

Print one report for each pair, in the order the pairs are given.

Each report consists of:

a header line and a line of dashes;
one line for every leg of the shortest route, showing the leg's start city, end city, route name and mileage;
a line of dashes under the Miles column, followed by a Total line giving the total mileage.

The columns are fixed width and separated by a single space: From and To are 20 characters wide and left-justified, Route is 10 characters wide and left-justified, and Miles is 5 characters wide and right-justified.

Two blank lines precede each report, except that a single blank line precedes the first report.

There are no extraneous blanks in the input. The map has at most 100 cities and at most 200 highway segments, and the total length of each shortest route fits in a 16-bit integer. For every pair, the shortest route is unique.

Examples3

Example 1

Input

San Luis Obispo,Bakersfield,CA-58,117
Bakersfield,Mojave,CA-58,65
Mojave,Barstow,CA-58,70
Barstow,Baker,I-15,62
Baker,Las Vegas,I-15,92
San Luis Obispo,Santa Barbara,US-101,106
San Luis Obispo,Santa Barbara,CA-1,113
Santa Barbara,Los Angeles,US-101,95
Bakersfield,Wheeler Ridge,CA-99,24
Wheeler Ridge,Los Angeles,I-5,88
Mojave,Los Angeles,CA-14,94
Los Angeles,San Bernardino,I-10,65
San Bernardino,Barstow,I-15,73
Los Angeles,San Diego,I-5,121
San Bernardino,San Diego,I-15,103

Santa Barbara,Las Vegas
San Diego,Los Angeles
San Luis Obispo,Los Angeles

Expected output


From                 To                   Route      Miles
-------------------- -------------------- ---------- -----
Santa Barbara        Los Angeles          US-101        95
Los Angeles          San Bernardino       I-10          65
San Bernardino       Barstow              I-15          73
Barstow              Baker                I-15          62
Baker                Las Vegas            I-15          92
                                                     -----
                                          Total        387


From                 To                   Route      Miles
-------------------- -------------------- ---------- -----
San Diego            Los Angeles          I-5          121
                                                     -----
                                          Total        121


From                 To                   Route      Miles
-------------------- -------------------- ---------- -----
San Luis Obispo      Santa Barbara        US-101       106
Santa Barbara        Los Angeles          US-101        95
                                                     -----
                                          Total        201

Example 2

Input

A,B,R1,10

A,B

Expected output


From                 To                   Route      Miles
-------------------- -------------------- ---------- -----
A                    B                    R1            10
                                                     -----
                                          Total         10

Example 3

Input

A,B,Direct,100
A,C,R1,10
C,B,R2,20

A,B

Expected output


From                 To                   Route      Miles
-------------------- -------------------- ---------- -----
A                    C                    R1            10
C                    B                    R2            20
                                                     -----
                                          Total         30