USACO 2014 December Contest, Silver Problem 1. Piggyback

原题下载

USACO2014-DEC-S1

答案

(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 XX. Then from XX, we can use a BFS to calculate the fastest paths to all the other fields. Then if it takes DiDi edges to travel from field XX to field ii, the answer is BD1+ED2+PDNB∗D1+E∗D2+P∗DN.

This already gives us an O(N2)O(N2) solution; just try out each XX. To speed it up to O(N)O(N), notice that we always want the distances from fields 11, 22, and NN. So if we precompute those distances, it takes O(1)O(1) time to try out each XX.

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);
}
翰林国际教育资讯二维码