BZOJ 3891 [Usaco2014 Dec]Piggy Back BFS

题目大意：给定一张无向图，第一个人从点1出发每走一条边消耗A，第二个人从点2出发每走一条边消耗B，两个人相遇后一起走每走一条边消耗C，两个人到达点n的最小花销

分别从点1、点2、点n出发BFS一遍，预处理出每个点到点1、点2、点n的最短路

然后枚举两人相遇的点，计算消耗之和即可

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 40400
using namespace std;
struct abcd{
	int to,next;
}table[M<<1];
int head[M],tot;
int n,m,A,B,C;
long long ans=2147483647;
int f[M],g[M],t[M];
int q[M],r,h;
bool v[M];
void Add(int x,int y)
{
	table[++tot].to=y;
	table[tot].next=head[x];
	head[x]=tot;
}
void BFS(int f[])
{
	int i;
	while(r!=h)
	{
		int x=q[++h];
		for(i=head[x];i;i=table[i].next)
			if(!v[table[i].to])
			{
				v[table[i].to]=true;
				q[++r]=table[i].to;
				f[table[i].to]=f[x]+1;
			}
	}
}
int main()
{
	int i,x,y;
	cin>>A>>B>>C>>n>>m;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		Add(x,y);Add(y,x);
	}
	memset(v,0,sizeof v);r=h=0;v[q[++r]=1]=true;BFS(f);
	memset(v,0,sizeof v);r=h=0;v[q[++r]=2]=true;BFS(g);
	memset(v,0,sizeof v);r=h=0;v[q[++r]=n]=true;BFS(t);
	for(i=1;i<=n;i++)
		ans=min(ans,(long long)A*f[i]+B*g[i]+C*t[i]);
	cout<<ans<<endl;
	return 0;
}

BZOJ 3891 [Usaco2014 Dec]Piggy Back BFS

原文：http://blog.csdn.net/popoqqq/article/details/43971603