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

#include<fstream>
#include<queue>
#include<cmath>
#include<cstring>
#include<ctime>
#define MAXN 40001
#define INF 0x7fffffff
using namespace std;
ifstream fin("piggyback.in");
ofstream fout("piggyback.out");
int N,M,B,E,P;
int d[3][MAXN],l[MAXN],p[3]={1,2};
queue<int>m[MAXN];
void BFS(int s)
{
	queue<int>q;bool v[MAXN];
	memset(v,0,sizeof(v));
	q.push(p[s]);v[p[s]]=1;d[s][p[s]]=0;
	while(!q.empty())
	{
		int U=q.front();
		q.pop();
		for(int i=1;i<=l[U];i++)
		{
			int V=m[U].front();
			m[U].pop();m[U].push(V);
			if(v[V]) continue;
			q.push(V);v[V]=1;
			d[s][V]=d[s][U]+1;
		}
	}
}
void INPUT()
{
	memset(l,0,sizeof(l));
	fin>>B>>E>>P>>N>>M;
	int u,v;
	for(int i=1;i<=M;i++)
	{
		fin>>u>>v;
		m[u].push(v);m[v].push(u);
		l[u]++;l[v]++;
	}
	p[2]=N;
}
void WORK()
{
	int bm,em,pm=INF;
	for(int i=0;i<3;i++) BFS(i);
	bm=d[0][N]*B;em=d[1][N]*E;
	for(int i=1;i<=N;i++)
		if((d[0][i]>0||i==1)&&(d[1][i]>0||i==2)&&d[2][i]>0)
			pm=min(pm,d[0][i]*B+d[1][i]*E+d[2][i]*P);
	fout<<min(bm+em,pm)<<endl;
}
int main()
{
	INPUT();
	WORK();
	return 0;
}