# USACO 2015 January Contest, Bronze Problem 1. Cow Routing

USACO2015JAN-B1

(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;
}```