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