BZOJ 3891 [Usaco2014 Dec]Piggy Back

题目大意

两个人分别从1,2号点出发前往N号点。第一个人走一步花费a,第二个人走一步花费b,两个人一起走一步总共花费c.求二人全部抵达N的最小花费。

Dijkstra.

令$dis[0][i]$表示第一个人走到$i$的最小花费，$dis[1][i]$表示第二个人走到$i$的最小花费，$dis[1][i]$表示两个人从$i$走到$N$的最小花费.找一个点求一下$dis[0],[1],[2]$的和就可以了。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define N 40010

int b,e,p,n,m,ix,iy,dis[3][N],ans=0x3f3f3f3f;

int to[N<<1],nex[N<<1],head[N],tot;

priority_queue<pair<int,int> >q;

inline int RI()
{
	int ret=0;
	char tmp=getchar();
	while(tmp<'0'||tmp>'9') tmp=getchar();
	while(tmp>='0'&&tmp<='9') ret=ret*10+tmp-'0',tmp=getchar();
	return ret;
}

inline void AE(int tx,int ty) {to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot;}

inline void dij()
{
	memset(dis,0x3f,sizeof dis);
	dis[0][1]=0;
	q.push(pair<int,int>(0,1));
	while(!q.empty())
	{
		int tmp=q.top().second;
		q.pop();
		for(int i=head[tmp];i;i=nex[i])
			if(dis[0][to[i]]>dis[0][tmp]+b)
			{
				dis[0][to[i]]=dis[0][tmp]+b;
				q.push(pair<int,int>(-dis[0][to[i]],to[i]));
			}
	}
	dis[1][2]=0;
	q.push(pair<int,int>(0,2));
	while(!q.empty())
	{
		int tmp=q.top().second;
		q.pop();
		for(int i=head[tmp];i;i=nex[i])
			if(dis[1][to[i]]>dis[1][tmp]+e)
			{
				dis[1][to[i]]=dis[1][tmp]+e;
				q.push(pair<int,int>(-dis[1][to[i]],to[i]));
			}
	}
	dis[2][n]=0;
	q.push(pair<int,int>(0,n));
	while(!q.empty())
	{
		int tmp=q.top().second;
		q.pop();
		for(int i=head[tmp];i;i=nex[i])
			if(dis[2][to[i]]>dis[2][tmp]+p)
			{
				dis[2][to[i]]=dis[2][tmp]+p;
				q.push(pair<int,int>(-dis[2][to[i]],to[i]));
			}
	}
}

int main()
{
	b=RI(),e=RI(),p=RI(),n=RI(),m=RI();
	while(m--) ix=RI(),iy=RI(),AE(ix,iy),AE(iy,ix);
	dij();
	for(int i=1;i<=n;++i)
		ans=min(ans,dis[0][i]+dis[1][i]+dis[2][i]);
	printf("%d\n",ans);
}