USACO 5.4 Canada Tour

For every pair of cities (i,j) find maximum total length of two paths. One path starts at city 1 and ends in city i, the other path starts from city 1 and ends in city j. Both path have no common cities except the start city 1 and the end city N. First path will reach city N, and the result will be the maximum value of the other path ending at j where 1 <= j <= N.

#include <vector>
#include <iostream>
#include <fstream>
#include <unordered_map>
#include <string>

using namespace std;

int N, V;
vector<vector<int>> dp;
vector<vector<bool>> flight;
unordered_map<string, int> cities;

int main() {
    ifstream fin("tour.in");
    ofstream fout("tour.out");

    fin >> N >> V;
    dp = vector<vector<int>>(N + 1, vector<int>(N + 1));
    flight = vector<vector<bool>>(N + 1, vector<bool>(N + 1, false));
    
    string city;
    for (int i = 1; i <= N; ++i) {
        fin >> city;
        cities[city] = i;
    }
    
    string from, to;
    for (int i = 0; i < V; ++i) {
        fin >> from >> to;
        flight[cities[from]][cities[to]] = true;
        flight[cities[to]][cities[from]] = true;
    }
    
    dp[1][1] = 1;
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            for (int k = 1; k < j; ++k) {
                if (dp[i][k] && flight[k][j]) {
                    dp[i][j] = std::max(dp[i][k] + 1, dp[i][j]);
                }
                dp[j][i] = dp[i][j];
            }
        }
    }
    
    int ans = 1;
    for (int i = 1; i <= N; ++i) {
        if (!flight[i][N]) continue;
        ans = std::max(ans, dp[i][N]);
    }
    
    cout << ans << endl;
    fout << ans << endl;
}