USACO 2015 January Contest, Bronze Problem 2. Cow Routing II

原题下载

USACO2015JAN-B2

答案

(Analysis by Mark Gordon)

This problem is a harder version of the Cow Routing problem that appeared earlier in the bronze contest. In this problem Bessie may use up to two tickets instead of just a single ticket.

One way to solve this problem is to try each intermediate city and use the same strategy as in the original problem to see which routes can take us from A to uu and which can take us from u to BB and take the cheapest pair of tickets. However the naive approach takes O(CNM) time (where C is the number of cities and M is the maximum length of each route) which is a bit too slow to pass all of the test cases.

To amend this we can simply do most of the work for intermediate city simultaneously. We'll keep an array ca2u to represent the minimum route cost to go from city A to city u and similarly cu2b to give the minimum route cost to go from city u to city B. If we can successfully calculate these two arrays then the final answer is just the minimum cost of ca2u[u]+cu2b[u] over each candidate city u.

We can calculate this array in O(NM) time by just updating ca2u[u] for any city u that appears after city A in a route. Similarly, we do the same for cu2b[u] for any city u that appears before city B in a route. This yields a solution like below.

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

int main() {
  freopen("cowroute.in", "r", stdin);
  freopen("cowroute.out", "w", stdout);

  int A, B, N;
  cin >> A >> B >> N;

  /* Read the costs and routes. */
  vector<int> costs(N);
  vector<vector<int> > routes(N);
  for (int i = 0; i < N; i++) {
    int ln;
    cin >> costs[i] >> ln;
    routes[i].resize(ln);
    for (int j = 0; j < ln; j++) {
      cin >> routes[i][j];
    }
  }

  /* ca2u[u] gives the cheapest route cost from A to u. */
  vector<int> ca2u(10001, 100000);
  ca2u[A] = 0;

  /* D2[u] gives the cheapest route cost form u to B. */
  vector<int> cu2b(10001, 100000);
  cu2b[B] = 0;

  /* Update D1 and D2 based on each route. */
  for (int i = 0; i < N; i++) {
    int cost = costs[i];
    vector<int>& route = routes[i];

    /* Determine the position of A and B in the route, if present. */
    int pos_a = route.size();
    int pos_b = -1;
    for (int j = 0; j < route.size(); j++) {
      if (route[j] == A) {
        pos_a = j;
      } else if (route[j] == B) {
        pos_b = j;
      }
    }

    /* For each city u after A update D1[u].  Similarly update D2[u] for each
     * city u before B. */
    for (int j = 0; j < route.size(); j++) {
      if (pos_a <= j) {
        ca2u[route[j]] = min(ca2u[route[j]], cost);
      }
      if (j <= pos_b) {
        cu2b[route[j]] = min(cu2b[route[j]], cost);
      }
    }
  }

  /* Calculate the minimum cost for each possible intermediate node. */
  int result = 100000;
  for (int i = 1; i <= 10000; i++) {
    result = min(result, ca2u[i] + cu2b[i]);
  }

  /* Output the minimum cost pair (or single) ticket, if possible. */
  if (result == 100000) {
    cout << -1 << endl;
  } else {
    cout << result << endl;
  }

  return 0;
}