(Analysis by Mark Gordon)

This problem asks us to find the minimum cost route that allows us to fly from city A to city B. This is a relatively straightforward problem and can be solved simply by testing if city A appears before city B in each route and taking the minimum cost over all such routes.

We can do this by using a boolean flag to indicate if we have already seen city A in the route. If we see city B when that flag is set then it must be possible to go from A to B using that route. In fact, there's no need to even store the route in an array!

#include <iostream> #include <cstdio> using namespace std; #define INF (int)1e9 int main() { freopen("cowroute.in", "r", stdin); freopen("cowroute.out", "w", stdout); int A, B, N; cin >> A >> B >> N; int result = INF; for (int i = 0; i < N; i++) { int cost, sz; cin >> cost >> sz; /* Loop over the route. */ bool found = false; for (int j = 0; j < sz; j++) { int city; cin >> city; if (city == A) { /* Note that we've seen city A. */ found = true; } if (found && city == B) { /* If we visit city B after city A then this flight is usable. */ result = min(result, cost); } } } /* Output the min cost ticket or report that no ticket is suitable. */ if (result == INF) { cout << "-1\n"; } else { cout << result << '\n'; } return 0; }