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

#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("piggyback.in");
ofstream out("piggyback.out");
int B,E,P,N,M;
int temp=0;
int best=9999999;
int ans1=0,ans2=0;
vector<int> g[40001],a,b;
bool l[40001]={0};
int f[40001][3]={0};
void clear()
{
	int i;
	for(i=1;i<=N;i++)l[i]=0;
}
void BFS(int s,int p)
{
	int i;
	queue<int> q;
	for(i=1;i<=N;i++)
	{
		l[i]=0;
		f[i][p]=9999999;
	}
	l[s]=1;
	f[s][p]=0;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		//l[u]=0;
		for(i=0;i<g[u].size();i++)
		{
			int v=g[u][i];
			//out<<v<<endl;
			if(f[v][p]>f[u][p]+1)f[v][p]=f[u][p]+1;
			if(!l[v])
			{
			    l[v]=1;
				q.push(v);
			}
		}
	}
}
int main()
{
	int i,j,aa,bb;
	int temp=0;
	int best=9999999;
	in>>B>>E>>P>>N>>M;
	for(i=1;i<=M;i++)
	{
		in>>aa>>bb;
		g[aa].push_back(bb);
		g[bb].push_back(aa);
	}
	//out<<B<<' '<<E<<' '<<P<<endl;
	BFS(1,0);
	clear();
	BFS(2,1);
	clear();
	BFS(N,2);
	/*for(i=1;i<=N;i++)
	{
		out<<f[i][0]<<' '<<f[i][1]<<' '<<f[i][2]<<endl;
	}*/
	for(i=1;i<=N;i++)
	{
		temp=f[i][0]*B+f[i][1]*E+f[i][2]*P;
		//out<<temp<<endl;
		if(temp<best)best=temp;
	}
	out<<best<<endl;
	return 0;
}