USACO 2014 December Contest, Silver Problem 1. Piggyback

答案

(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 B?D1+E?D2+P?DNB?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);
}

以上就是關(guān)于【USACO 2014 December Contest, Silver Problem 1. Piggyback】的解答，如需了解學(xué)校/賽事/課程動(dòng)態(tài)，可至翰林教育官網(wǎng)獲取更多信息。

往期文章閱讀推薦：

2027 USAAIO人工智能奧賽報(bào)名進(jìn)行中！Round 1新規(guī)出爐，2月開賽如何備考？

外灘大會(huì)見證AI爆發(fā)！緊跟智能時(shí)代，從USACO計(jì)算機(jī)奧賽起步！