记录编号	159642	评测结果	AAAAAAAAAAA
题目名称	背驮式行走	最终得分	100
用户昵称	hzoi55223	是否通过	通过
代码语言	C++	运行时间	0.057 s
提交时间	2015-04-22 12:22:05	内存使用	1.84 MiB

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

struct line{
	int to,next;
}	h[100010];
int n,m,sum,g[40010],dis[40010][4];
long long b,e,p,now,ans;

void ADD(int st,int en){
	sum++;	h[sum].to=en;	h[sum].next=g[st];	g[st]=sum;
	sum++;	h[sum].to=st;	h[sum].next=g[en];	g[en]=sum;
}

void init(){
	int x,y;	sum=0;
	scanf("%lld%lld%lld%d%d",&b,&e,&p,&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&x,&y);	ADD(x,y);
	}
}

void SPFA(int k,int r){
	int x,y;
	bool v[40010];
	queue<int> q;
	for(int i=1;i<=n;++i)	dis[i][r]=0x7fffffff/3;
	q.push(k);	v[k]=1;	dis[k][r]=0;
	while(!q.empty()){
		x=q.front();
		for(int i=g[x];i!=0;i=h[i].next){
			y=h[i].to;
			if(dis[x][r]+1<dis[y][r]){
				dis[y][r]=dis[x][r]+1;
				if(!v[y]){
					v[y]=1;	q.push(y);
				}
			}
		}
		q.pop();	v[x]=0;
	}
}

void work(){
	SPFA(1,1);	SPFA(2,2);	SPFA(n,3);
	ans=b*dis[1][3]+e*dis[2][3];
	for(int i=1;i<n;++i){
		if(dis[i][1]==0x7fffffff/3||dis[i][2]==0x7fffffff/3||
			dis[i][3]==0x7fffffff/3)	continue;
		now=b*dis[i][1]+e*dis[i][2]+p*dis[i][3];
		if(now<ans)	ans=now;
	}
	printf("%lld\n",ans);
}

int main(){
	freopen("piggyback.in","r",stdin);
	freopen("piggyback.out","w",stdout);
	init();
	work();
	fclose(stdin);
	fclose(stdout);
	return 0;
}