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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const LL INF=1e15;
const int SIZEN=40010;
int N,M;
LL B,E,P;
vector<int> c[SIZEN];
int fb[SIZEN],fe[SIZEN],fp[SIZEN];
bool vis[SIZEN]={0};
queue<int> Q;
void BFS(int S,int f[]){
	memset(vis,0,sizeof(vis));
	vis[S]=true;f[S]=0;Q.push(S);
	while(!Q.empty()){
		int x=Q.front();Q.pop();
		for(int i=0;i<c[x].size();i++){
			int u=c[x][i];
			if(!vis[u]){
				vis[u]=true;
				f[u]=f[x]+1;
				Q.push(u);
			}
		}
	}
}
void read(void){
	cin>>B>>E>>P>>N>>M;
	int a,b;
	for(int i=1;i<=M;i++){
		scanf("%d%d",&a,&b);
		c[a].push_back(b);
		c[b].push_back(a);
	}
}
void work(void){
	BFS(1,fb);
	BFS(2,fe);
	BFS(N,fp);
	LL ans=INF;
	for(int i=1;i<=N;i++){
		LL now=B*fb[i]+E*fe[i]+P*fp[i];
		ans=min(ans,now);
	}
	cout<<ans<<endl;
}
int main(){
	freopen("piggyback.in","r",stdin);
	freopen("piggyback.out","w",stdout);
	read();
	work();
	return 0;
}