(Analysis by Jonathan Paulson - [email protected])

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