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

#include<deque>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
bool vis[40001];
int B,E,P,N,M,len,ans,g[40001],to[80001],next[80001],dis[40001][3];
void in(int &x){
    int ch;
    while((ch=getchar())<48);x=ch-48;
    while((ch=getchar())>47) x=x*10+ch-48;
}
void add(int x,int y){
    to[++len]=y,next[len]=g[x],g[x]=len;
}
void spfa(int s){
    deque <int> q;
    if(s==N) s=dis[N][0]=0,q.push_back(N);
    else q.push_back(s),dis[s][s]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop_front(),vis[x]=0;
        for(int t,i=g[x];i;i=next[i])
            if(dis[t=to[i]][s]>dis[x][s]+1){
                dis[t][s]=dis[x][s]+1;
                if(!vis[t]){
                    vis[t]=1;
                    if(q.empty()||dis[t]<dis[q.front()]) q.push_front(t);
                    else q.push_back(t);
                }
            }
    }
}
int main(){
	freopen("piggyback.in","r",stdin);
	freopen("piggyback.out","w",stdout);
    in(B),in(E),in(P),in(N),in(M);
    for(int x,y;M--;) in(x),in(y),add(x,y),add(y,x);
    memset(dis,0x3f,sizeof dis);
    spfa(1),spfa(2),spfa(N),ans=0x7fffffff;
    for(int i=1;i<=N;i++) ans=min(ans,dis[i][1]*B+dis[i][2]*E+dis[i][0]*P);
    printf("%d",ans);
}