记录编号	159753	评测结果	AAAAAAAAAAA
题目名称	背驮式行走	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.078 s
提交时间	2015-04-22 16:49:24	内存使用	1.23 MiB

#include<fstream>
#include<vector>
#include<queue>
using namespace std;
const int MAX=2147483647;
int B,E,P,N,M;
vector<int>mp[40010];
int goB[40010]={0},goE[40010]={0},goN[40010]={0};
void first(int n){
	for(int i=1;i<=n;i++){
		goB[i]=MAX;
		goE[i]=MAX;
		goN[i]=MAX;
	}
}
void BFSB(){
	queue<int>ls;
	ls.push(1);
	goB[1]=0;
	int u;
	while(!ls.empty()){
		u=ls.front();
		ls.pop();
		for(int i=0;i<mp[u].size();i++)
			if(goB[mp[u][i]]==MAX){
				goB[mp[u][i]]=goB[u]+1;
				ls.push(mp[u][i]);
			}
	}
}
void BFSE(){
	queue<int>ls;
	ls.push(2);
	goE[2]=0;
	int u;
	while(!ls.empty()){
		u=ls.front();
		ls.pop();
		for(int i=0;i<mp[u].size();i++)
			if(goE[mp[u][i]]==MAX){
				goE[mp[u][i]]=goE[u]+1;
				ls.push(mp[u][i]);
			}
	}
}
void BFSN(){
	queue<int>ls;
	ls.push(N);
	goN[N]=0;
	int u;
	while(!ls.empty()){
		u=ls.front();
		ls.pop();
		for(int i=0;i<mp[u].size();i++)
			if(goN[mp[u][i]]==MAX){
				goN[mp[u][i]]=goN[u]+1;
				ls.push(mp[u][i]);
			}
	}
}
int main(){
	ifstream fi("piggyback.in");
	ofstream fo("piggyback.out");
	fi>>B>>E>>P>>N>>M;
	int a,b;
	for(int i=0;i<M;i++){
		fi>>a>>b;
		mp[a].push_back(b);
		mp[b].push_back(a);
	}
	first(N);
	BFSB();
	BFSE();
	BFSN();
	int end=MAX,u;
	for(int i=1;i<=N;i++){
		u=goB[i]*B+goE[i]*E+goN[i]*P;
		if(u<end)
			end=u;
	}
	fo<<end<<endl;
	return 0;
}