UVA 186

#define ll long long
#include <bits/stdc++.h>
using namespace std;

/*
Ordered set usage:
order_of_key (k) : Number of items strictly smaller than k.
find_by_order(k) : K-th element in a set (counting from zero).
*/

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

const int OO = 1e9;
const double EPS = 1e-9;

struct edge {
    string from;
    string to;
    string name;
    int cost;

    int operator < (const edge &e) const {
        return cost > e.cost;
    }
};

int cnt_com(string &s) {
    int ret = 0;
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == ',') {
            ret++;
        }
    }
    return ret;
}

int nxt_com(string &s, int idx) {
    for(; idx < s.size(); idx++) {
        if(s[idx] == ',') {
            return idx;
        }
    }
    return -1;
}

map<string,vector<edge>> graph;

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    //freopen("out.txt","w",stdout);
    string in;
    while(getline(cin,in)) {
        if(cnt_com(in) == 3) {
            edge curr;
            int e1 = nxt_com(in,0);
            curr.from = in.substr(0,e1);
            int e2 = nxt_com(in,e1+1);
            curr.to = in.substr(e1+1,e2-e1-1);
            int e3 = nxt_com(in,e2+1);
            curr.name = in.substr(e2+1, e3-e2-1);
            int cost = stoi(in.substr(e3+1,in.size()-e3-1));
            curr.cost = cost;
            graph[curr.from].push_back(curr);
            swap(curr.from,curr.to);
            graph[curr.from].push_back(curr);
        }
        else {
            if(in.size() < 2) {
                continue;
            }
            map<string,edge> path;
            map<string,int> dist;
            priority_queue<edge> pq;
            int ce = nxt_com(in,0);
            string origin = in.substr(0,ce);
            string tgt = in.substr(ce+1,in.size()-ce-1);
            dist[origin] = 0;
            for(edge e : graph[origin]) {
                pq.push(e);
            }
            while(!pq.empty()) {
                edge curr = pq.top();
                pq.pop();
                if(dist.find(curr.to) != dist.end()) {
                    continue;
                }
                dist[curr.to] = curr.cost;
                path[curr.to] = curr;
                for(edge e : graph[curr.to]) {
                    if(dist.find(e.to) == dist.end()) {
                        e.cost += curr.cost;
                        pq.push(e);
                    }
                }
            }
            stack<edge> ans;
            string curr_p = tgt;
            while(curr_p != origin) {
                ans.push(path[curr_p]);
                curr_p = path[curr_p].from;
            }
            cout << "\n\nFrom" << string(17, ' ') << "To" << string(19, ' ') << "Route" << string(6, ' ') << "Miles\n";
            cout << string(20,'-') << ' ' << string(20,'-') << ' ' << string(10,'-') << ' ' << string(5,'-') << "\n";
            int sum = 0;
            int prv = 0;
            while(!ans.empty()) {
                edge curr = ans.top();
                ans.pop();
                string curr_cost = to_string(curr.cost-prv);
                sum += curr.cost-prv;
                prv = curr.cost;
                cout << curr.from << string(21 - curr.from.size(),' ') << curr.to << string(21 - curr.to.size(),' ');
                cout << curr.name << string(11 - curr.name.size(),' ') << string(5-curr_cost.size(), ' ') << curr_cost << "\n";
            }
            string string_sum = to_string(sum);
            cout << string(53, ' ') << string(5, '-') << "\n";
            cout << string(42, ' ') << "Total" << string(6, ' ') << string(5 - string_sum.size(), ' ') << string_sum << "\n";
        }
    }
    return 0;
}