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

#include<iostream>
#include<fstream>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;
ifstream fin("piggyback.in");
ofstream fout("piggyback.out");
const int IMAX=99999999;
int B,E,P,N;
vector<vector<int> > TT;
vector<long long> dis;//最短时间
vector<long long> AA;//A到该点的最短时间
vector<long long> BB;//B到该点的最短距离
vector<bool> flag;
void core1(){
	queue<int> Q;
	Q.push(1);
	AA.resize(N+2,IMAX);
	AA[1]=0;
	flag.clear();
	flag.resize(N+2,0);
	flag[1]=1;
	while(!Q.empty()){
		int it=Q.front();
		Q.pop();
		flag[it]=0;
		for(int i=0;i!=TT[it].size();++i){
			if(AA[TT[it][i]]>AA[it]+B){
				AA[TT[it][i]]=AA[it]+B;
				if(flag[TT[it][i]]==0){
					flag[TT[it][i]]=1;
					Q.push(TT[it][i]);
				}
			}
		}
	}
}
void core2(){
	queue<int> Q;
	Q.push(2);
	BB.resize(N+2,IMAX);
	BB[2]=0;
	flag.clear();
	flag.resize(N+2,0);
	flag[2]=1;
	while(!Q.empty()){
		int it=Q.front();
		Q.pop();
		flag[it]=0;
		for(int i=0;i!=TT[it].size();++i){
			if(BB[TT[it][i]]>BB[it]+E){
				BB[TT[it][i]]=BB[it]+E;
				if(flag[TT[it][i]]==0){
					flag[TT[it][i]]=1;
					Q.push(TT[it][i]);
				}
			}
		}
	}

}
long long core3(){
	queue<int> Q;
	Q.push(N);
	flag.clear();
	flag.resize(N+3,0);
	flag[N]=1;
	dis.resize(N+2,IMAX);
	dis[N]=0;
	while(!Q.empty()){
		int it=Q.front();
		Q.pop();
		flag[it]=0;
		for(int i=0;i!=TT[it].size();++i){
			if(dis[TT[it][i]]>=dis[it]+P){
				dis[TT[it][i]]=dis[it]+P;
				if(flag[TT[it][i]]==0){
					flag[TT[it][i]]=1;
					Q.push(TT[it][i]);
				}
			}
		}
	}
	long long mmin=IMAX;
	for(int i=0;i!=dis.size();++i){
		mmin=min(mmin,dis[i]+AA[i]+BB[i]);
	}
	return mmin;
}
int main(){
	int m;
	fin>>B>>E>>P>>N>>m;
	TT.resize(N+2);
	for(int i=0;i!=m;++i){
		int a,b;
		fin>>a>>b;
		TT[a].push_back(b);
		TT[b].push_back(a);
	}
	core1();core2();
	fout<<core3()<<endl;
	return 0;
}
//designed by wolf