记录编号	159750	评测结果	AAAAAAAAAAA
题目名称	背驮式行走	最终得分	100
用户昵称	黑夜<=>白天	是否通过	通过
代码语言	C++	运行时间	0.071 s
提交时间	2015-04-22 16:41:02	内存使用	5.82 MiB

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
using namespace std;
int u[200000],v[200000];
int first[200000],next[200000];
int dis1[60000],dis2[60000],disz[60000];
int team[600000];
bool b[60000]={0};
const int Max=0x7fffffff/3;
int main()
{
	freopen("piggyback.in","r",stdin);
	freopen("piggyback.out","w",stdout);
	int c,e,p,n,m;
	scanf("%d%d%d%d%d",&c,&e,&p,&n,&m);
	for(int i=1;i<=m*2;++i)
	{
		scanf("%d%d",&u[i],&v[i]);
		next[i]=first[u[i]];
		first[u[i]]=i;
		++i;
		v[i]=u[i-1];
		u[i]=v[i-1];
		next[i]=first[u[i]];
		first[u[i]]=i;
	}
	
	int head=1;
	int tail=1;
	for(int i=1;i<=n;++i)
	{
		dis1[i]=Max;
	}
	dis1[1]=0;
	team[head]=1;
	b[1]=1;
	while(head<=tail)
	{
		int k=first[team[head]];
		while(k!=0)
		{
			if(dis1[v[k]]>dis1[u[k]]+1)
			{
				dis1[v[k]]=dis1[u[k]]+1;
				if(b[v[k]]==0)
				{
					++tail;
					team[tail]=v[k];
					b[v[k]]=1;
				}
			}
			k=next[k];
		}
		b[team[head]]=0;
		++head;
	}
	head=1;
	tail=1;
	for(int i=1;i<=n;++i)
	{
		dis2[i]=Max;
	}
	memset(b,0,sizeof(b));
	dis2[2]=0;
	team[head]=2;
	b[2]=1;
	while(head<=tail)
	{
		int k=first[team[head]];
		while(k!=0)
		{
			if(dis2[v[k]]>dis2[u[k]]+1)
			{
				dis2[v[k]]=dis2[u[k]]+1;
				if(b[v[k]]==0)
				{
					++tail;
					team[tail]=v[k];
					b[v[k]]=1;
				}
			}
			k=next[k];
		}
		b[team[head]]=0;
		++head;
	}
	head=1;
	tail=1;
	for(int i=1;i<=n;++i)
	{
		disz[i]=Max;
	}
	memset(b,0,sizeof(b));
	disz[n]=0;
	team[head]=n;
	b[n]=1;
	while(head<=tail)
	{
		int k=first[team[head]];
		while(k!=0)
		{
			if(disz[v[k]]>disz[u[k]]+1)
			{
				disz[v[k]]=disz[u[k]]+1;
				if(b[v[k]]==0)
				{
					++tail;
					team[tail]=v[k];
					b[v[k]]=1;
				}
			}
			k=next[k];
		}
		b[team[head]]=0;
		++head;
	}
	
	
	long long ans=Max;
	for(int i=1;i<=n;++i)
	{
		//printf("%d %d %d %d\n",dis1[i],dis2[i],disz[i],i);
		long long sum=c*dis1[i]+e*dis2[i]+p*disz[i];
		if(sum<ans)
		{
			ans=sum;
		}
	}
	
	printf("%lld\n",ans);
	return 0;
	
	
}