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