记录编号	159690	评测结果	AAAAAAAAAAA
题目名称	背驮式行走	最终得分	100
用户昵称	RP++	是否通过	通过
代码语言	C++	运行时间	0.052 s
提交时间	2015-04-22 13:55:52	内存使用	1.73 MiB

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

#define maxn 40010
#define maxm 100010
#define INF 0x3fffffff

int tot, b, e, p, n, m;;
int head[maxn], to[maxm], next[maxm];
int dis1[maxn], dis2[maxn], disn[maxn];
bool inq[maxn];

void Build(int s, int t) {
	to[++tot] = t, next[tot] = head[s], head[s] = tot;
}

void spfa(int s, int *dis) {
	for(int i = 1; i <= n; i++)
		dis[i] = INF, inq[s] = 0;
	queue<int>q; q.push(s);
	dis[s] = 0, inq[s] = 1;
	while(!q.empty()) {
		int p = q.front(); q.pop();
		inq[p] = 0;
		for(int i = head[p]; i; i = next[i]) {
			int l = to[i];
			if(dis[l] > dis[p] + 1) {
				dis[l] = dis[p] + 1;
				if(!inq[l]) {
					inq[l] = true; q.push(l);
				}
			}
		}
	}
}

int main() {
	freopen("piggyback.in", "r", stdin);
	freopen("piggyback.out", "w", stdout);
	scanf("%d%d%d%d%d", &b, &e, &p, &n, &m);
	int u, v;
	for(int i = 1; i <= m; i++) {
		scanf("%d%d", &u, &v);
		Build(u, v), Build(v, u);
	}
	spfa(1, dis1), spfa(2, dis2), spfa(n, disn);
	int ans = dis1[n] * b + dis2[n] * e;
	for(int i = 1; i <= n; i++) {
		int tmp = dis1[i] * b + dis2[i] * e + disn[i] * p;
		if(tmp < ans) ans = tmp;
	}
	printf("%d", ans);
}