Transport (TLAC) Complete Solution using C++

#include <bits/stdc++.h>

using namespace std;

/*

SAMPLE TESTCASE 0:
    4
    JUU 2
    JFK 3
    JER 3
    JRU 2
    JFK 2 JER 3
    JUU 2 JER 1 JRU 18
    JUU 3 JFK 1 JRU 3
    JFK 18 JER 3
    JUU JRU
SAMPLE OUTPUT 0 = JUU->JER->JRU

SAMPLE TESTCASE 1:
    4
    JUU 2
    JFK 3
    JER 3
    JRU 2
    JFK 2 JER 4
    JUU 2 JER 1 JRU 18
    JUU 3 JFK 1 JRU 3
    JFK 18 JER 3
    JUU JRU
SAMPLE OUTPUT 1 = JUU->JFK->JER->JRU

*/

vector<string> cities;
vector<int> connected;
vector<vector<int>> a;
vector<vector<int>> cost;
vector<int> path;
vector<vector<int>> all;

int ConvertCity(string city) {
    for (int i = 0; i < (int) cities.size(); i++) {
        if (cities[i] == city) {
            return i;
        }
    }
    return -1;
}

void FindPath(int origin, int destination, vector<bool> visited) {
    visited[origin] = true;
    path.emplace_back(origin);
    if (origin == destination) {
        all.emplace_back(path);
    } else {
        for (auto it = a[origin].begin(); it != a[origin].end(); it++) {
            if (!visited[*it]) {
                FindPath(*it, destination, visited);
            }
        }
    }
    visited[origin] = false;
    path.pop_back();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    cities = vector<string>(n);
    connected = vector<int>(n);
    for (int i = 0; i < n; i++) {
        cin >> cities[i] >> connected[i];
    }
    a = vector<vector<int>>(n);
    cost = vector<vector<int>>(n, vector<int>(n, 0));
    for (int u = 0; u < n; u++) {
        for (int i = 0; i < (int) connected[u]; i++) {
            string city;
            int weight;
            cin >> city >> weight;
            int v = ConvertCity(city);
            a[u].emplace_back(v);
            cost[u][v] = weight;
        }
    }
    string start, end;
    cin >> start >> end;
    vector<bool> visited(n, false);
    FindPath(ConvertCity(start), ConvertCity(end), visited);
    int min_weight = INT_MAX;
    int min_count = INT_MAX;
    vector<string> res;
    for (int u = 0; u < (int) all.size(); u++) {
        int total = 0;
        vector<string> collect;
        for (int v = 0; v < (int) all[u].size(); v++) {
            if (v < (int) all[u].size() - 1) {
                total += (cost[all[u][v]][all[u][v + 1]]);
            }
            collect.emplace_back(cities[all[u][v]]);
        }
        if (total < min_weight) {
            min_weight = total;
            min_count = (int) all[u].size();
            res = collect;
        } else if (total == min_weight && (int) all[u].size() < min_count) {
            min_count = (int) all[u].size();
            res = collect;
        }
    }
    for (int i = 0; i < (int) res.size(); i++) {
        if (i > 0) {
            cout << "->";
        }
        cout << res[i];
    }
    cout << '\n';
    return 0;
}