03. Space Travel

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <limits>
#include <algorithm>

using namespace std;

int main() {
    string planet, line;
    getline(cin, planet);

    vector<string> planets;

    while (planet != "END") {
        planets.push_back(planet);
        getline(cin, planet);
    }

    vector<vector<int>> timeRoutes;

    int minTime = numeric_limits<int>::max(),
        maxTime = 0;

    for (int r = 0; r < planets.size(); r++) {
        getline(cin, line);

        istringstream ss(line);

        vector<int> times;

        int time;

        while (ss >> time) {
            times.push_back(time);
            if (time > maxTime) {
                maxTime = time;
            }
            if (time > 0 && time < minTime) {
                minTime = time;
            }
        }
        timeRoutes.push_back(times);
    }

    vector<int> routes;

    getline(cin, line);

    while (line != "END") {
        vector<string> route;

        istringstream ss(line);

        while (ss >> planet) {
            route.push_back(planet);
        }

        int time = 0, row, col;

        for (size_t i = 0; i < route.size() - 1; i++) {
            row = distance(planets.begin(), find(planets.begin(), planets.end(), route[i])),
                col = distance(planets.begin(), find(planets.begin(), planets.end(), route[i + 1]));
            time += timeRoutes[row][col];
        }

        routes.push_back(time);

        getline(cin, line);
    }

    for (int t : { minTime, maxTime }) {
        for (size_t r = 0; r < timeRoutes.size(); r++) {
            for (size_t c = 0; c < timeRoutes.size(); c++) {
                if (t == timeRoutes[r][c]) {
                    cout << t << ": " << planets[r] << " -> " << planets[c] << endl;
                }
            }
        }
    }

    int totalTime = 0;

    for (auto& t : routes) {
        cout << t << endl;
        totalTime += t;
    }

    cout << totalTime << endl;

    return 0;
}