Trip Routing

Your employer, the California Car Club (CCC), has decided to provide a trip routing service to its members. Your job is to write a program which reads a list of departure point-destination point pairs and calculates the shortest routes between them. For each trip, your program will print a report which itemises the names of each city passed through, with route names and leg distances.

Input

Input to your program will be in two parts.

The first part is a map in the form of a list of highway segments. Each segment is designated by a line containing four fields which are separated by commas. The first two fields are 1-20 characters each, and are the names of the cities which are at each end of the highway segment. The third field is the 1-10 character name of the route. The fourth field is the number of miles between the two endpoints, expressed as a positive integer. The highway segment list will be terminated by an empty line.

The second part of the input is a list of departure point-destination point pairs, one per line. The departure point is given first, followed by a comma and the destination point. Each of the cities is guaranteed to have appeared in the first part of the input data, and there will be a path that connects them. The list is terminated by the end of file.

Output

The output should be a series of reports, one for each departure point-destination point pair in the input. Each report should be in exactly the same form as those in the example below. There should be two blank lines before each report (including the first one).

Sample 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

Sample 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

Note: There will be no extraneous blanks in the input. There will be no more than 100 cities in the map and no more than 200 highway segments. The total distance in each best route is guaranteed to fit within a 16-bit integer.

#include <stdio.h>
#include <map>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;
struct E {
    string route;
    int miles;
    int to;
    E(string a, int b, int c):
        route(a), miles(b), to(c) {}
};
vector<E> g[1005];
int main() {
    char s[1005];
    map<string, int> R;
    string name[1005];
    int size = 0;
    while(gets(s)) {
        if(s[0] == '\0')    break;
        char w1[50], w2[50], w3[50];
        int w1len = 0, w2len = 0, w3len = 0;
        int i, cost;
        for(i = 0; s[i] != ','; i++)
            w1[w1len++] = s[i];
        for(i++; s[i] != ','; i++)
            w2[w2len++] = s[i];
        for(i++; s[i] != ','; i++)
            w3[w3len++] = s[i];
        sscanf(s+i+1, "%d", &cost);
        w1[w1len] = w2[w2len] = w3[w3len] = '\0';
        int &x = R[w1];
        int &y = R[w2];
        if(x == 0)  x = ++size;
        if(y == 0)  y = ++size;
        g[x].push_back(E(w3, cost, y));
        g[y].push_back(E(w3, cost, x));
    }
    for(map<string, int>::iterator it = R.begin();
        it != R.end(); it++) {
        name[it->second] = it->first;
    }
    while(gets(s)) {
        puts("\n");//two blank
        char w1[50], w2[50];
        int w1len = 0, w2len = 0;
        int i, j, k;
        for(i = 0; s[i] != ','; i++)
            w1[w1len++] = s[i];
        for(i++; s[i] != ','; i++)
            w2[w2len++] = s[i];
        w1[w1len] = w2[w2len] = '\0';
        int st = R[w1], ed = R[w2];
        int dist[1005] = {}, inq[1005] = {};
        int prev[1005];
        vector<E>::iterator path[1005];
        memset(dist, 63, sizeof(dist));
        queue<int> Q;
        Q.push(ed);
        dist[ed] = 0;
        while(!Q.empty()) {
            int tn = Q.front();
            Q.pop();
            inq[tn] = 0;
            for(vector<E>::iterator it = g[tn].begin();
                it != g[tn].end(); it++) {
                if(dist[it->to] > dist[tn] + it->miles) {
                    dist[it->to] = dist[tn] + it->miles;
                    prev[it->to] = tn;
                    path[it->to] = it;
                    if(inq[it->to] == 0) {
                        inq[it->to] = 1;
                        Q.push(it->to);
                    }
                }
            }
        }
        puts("From                 To                   Route      Miles");
        puts("-------------------- -------------------- ---------- -----");
        int x = st, mm = 0;
        while(x != ed) {
            printf("%-20s %-20s %-10s %5d\n", name[x].c_str(), name[prev[x]].c_str(), (path[x]->route).c_str(), path[x]->miles);
            x = prev[x];
        }
        puts("                                                     -----");
        printf("                                          Total       %4d\n", dist[st]);
    }
    return 0;
}