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

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int t1,t2,t3,n,m;
class student
{
public:
	int l[3];
	vector<int> son;
}a[400005];
int change(int p)
{
	if(p==1) return 0;
	if(p==2) return 1;
	if(p==n) return 2;
}
void count(int p)
{
	int u;
	bool b[40005]={0};
	queue<int> q;
	q.push(p);
	b[p]=1;
	a[p].l[change(p)]=0;
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		for(int i=0;i<a[u].son.size();i++)
		{
			if(!b[a[u].son[i]])
			{
			    q.push(a[u].son[i]);
				a[a[u].son[i]].l[change(p)]=a[u].l[change(p)]+1;
				b[a[u].son[i]]=1;
			}
		}
	}
}
void init()
{
	cin>>t1>>t2>>t3>>n>>m;
	int temp1,temp2;
	for(int i=1;i<=m;i++)
	{
		cin>>temp1>>temp2;
		a[temp1].son.push_back(temp2);
		a[temp2].son.push_back(temp1);
	}
	count(1);
	count(2);
	count(n);
}
void work()
{
	long long MIN=9999999;
	for(int i=1;i<=n;i++)
	{
		long long temp1=a[i].l[0]*t1+a[i].l[1]*t2+a[i].l[2]*t3;
	    long long temp2=a[i].l[0]*t1+a[i].l[1]*t2+a[i].l[2]*(t1+t2);
		if(temp1<MIN) MIN=temp1;
		if(temp2<MIN) MIN=temp2;
	}
	cout<<MIN;
}
int main()
{
	freopen("piggyback.in","r",stdin);
	freopen("piggyback.out","w",stdout);
	init();
	work();
	return 0;
}