USACO 2014 December Contest, Silver Problem 1. Piggyback

Category: 计算机国际竞赛 Date: 2017年12月5日上午11:10

答案

(Analysis by Jonathan Paulson - jonathanpaulson@gmail.com)

The first step is to see that we can break Bessie and Elsie's trip into two parts: the start until they meet and piggyback, and then piggybacking to the end (if they never piggyback, that's the same as meeting at the end and then piggybacking for 0 distance).

If we knew where they met, the problem would be easy. Suppose they meet at field $X$ . Then from $X$ , we can use a BFS to calculate the fastest paths to all the other fields. Then if it takes $D_{i}$ edges to travel from field $X$ to field $i$ , the answer is $B * D_{1} + E * D_{2} + P * D_{N}$ .

This already gives us an $O (N^{2})$ solution; just try out each $X$ . To speed it up to $O (N)$ , notice that we always want the distances from fields $1$ , $2$ , and $N$ . So if we precompute those distances, it takes $O (1)$ time to try out each $X$ .

Here's my C++ code for that solution:

#include <cstdio>
#include <vector>
#include <queue>

#define PB push_back

using namespace std;

typedef long long ll;

vector<ll> D(ll st, const vector<vector<ll>>& E) {
  vector<ll> D(E.size(), -1);

  deque<ll> Q;
  D[st] = 0;
  Q.PB(st);
  while(!Q.empty()) {
    ll x = Q.front(); Q.pop_front();
    for(ll y : E[x]) {
      if(D[y] == -1) {
        D[y] = D[x]+1;
        Q.PB(y);
      }
    }
  }
  return D;
}

int main() {
  ll b, e, p, n, m;
  scanf("%lld %lld %lld %lld %lld", &b, &e, &p, &n, &m);
  vector<vector<ll>> E(n, vector<ll>());
  for(ll i=0; i<m; i++) {
    ll x, y;
    scanf("%lld %lld", &x, &y);
    x--; y--;
    E[x].PB(y);
    E[y].PB(x);
  }

  vector<ll> D0 = D(0, E);
  vector<ll> D1 = D(1, E);
  vector<ll> Dn = D(n-1, E);

  ll ans = ll(1000)*1000*1000*1000;
  for(ll meet=0; meet<n; meet++) {
    ans = min(ans, D0[meet]*b + D1[meet]*e + Dn[meet]*p);
  }
  printf("%lld\n", ans);
}