洛谷P3110 [USACO14DEC]驮运Piggy Back

题目描述

贝西和她的妹妹艾尔斯白天在不同的地方吃草，而在晚上他们都想回到谷仓休息。聪明的牛仔，他们想出了一个计划，以尽量减少他们在步行时花费的总能量。

贝西在从田野走到相邻的地方时，花费B个能量单位，当她走到相邻的地方时，Elsie花费了E个能量单位。但是，如果Bessie和Elsie在同一个领域，Bessie可以携带Elsie在她的肩上，两者都可以移动到相邻的场地，而只花费P个能量单位（P可能比B + E小得多，Bessie的数量而Elsie会单独走到邻近的地方）。如果P非常小，最节能的解决方案可能涉及到Bessie和Elsie前往一个共同的会议场地，然后一起携带搭载旅行到谷仓的其余时间。当然，如果P很大，那么Bessie和Elsie可能最有意义的旅行

分别。在附注中，Bessie和Elsie对“背负”一词不满意，因为他们不明白为什么农场上的猪应该得到这种卓越形式的所有信用

运输。

给定B，E和P以及农场的布局，请计算Bessie和Elsie到达谷仓所需的最低能量。

Bessie和Elsie在不同的区域放牧，他们希望花费最小的能量返回谷仓。从一个区域走到一个相连区域，Bessie要花费B单位的能量，Elsie要花费E单位的能量。

如果某次他们两走到同一个区域，Bessie可以背着Elsie走路，花费P单位的能量走到另外一个相连的区域，满足P <B + E。

相遇后，他们可以一直背着走，也可以独立分开。

输入输出格式

输入格式：

INPUT :(文件piggyback.in）

第一行输入包含正整数B，E，P，N和M.所有这些最多为40,000。B，E和P如上所述。N是场中的字段数（编号为1..N，其中N> = 3），M是字段之间的连接数。Bessie和Elsie分别从1区和2区开始。谷仓住在田间N.

输入中的下一行M行描述了由两个字段的整数索引指定的一对不同字段之间的连接。连接是双向的。总是可以沿着一系列这样的连接从场1到场N，场2到场N。

输出格式：

OUTPUT：（文件piggyback.out）

一个整数，指定最小的能量Bessie和

Elsie集体需要花费到达谷仓。在例子中

这里显示，贝西从1到4，Elsie从2到3

然后，他们一起旅行从4到7到8。

输入输出样例

输入样例＃1：

输出样例＃1：

/*
    三遍bfs分别求以1,2，n为起点的最短路，然后枚举然后枚举两人相遇的点，计算消耗之和即可
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 40010
int bb,ee,p,n,m,num,head[maxn];
long long ans=9000000000;
int a[maxn],b[maxn],c[maxn];
struct node{
    int to,pre;
}e[maxn*2];
bool vis[maxn];
void Insert(int from,int to){
    e[++num].to=to;
    e[num].pre=head[from];
    head[from]=num;
}
void bfs(int start,int f[]){
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(start);
    vis[start]=1;
    while(!q.empty()){
        int now=q.front();q.pop();
        for(int i=head[now];i;i=e[i].pre){
            int to=e[i].to;
            if(!vis[to]){
                vis[to]=1;
                f[to]=f[now]+1;
                q.push(to);
            }
        }
    }
}
int main(){
    //freopen("Cola.txt","r",stdin);
    scanf("%d%d%d%d%d",&bb,&ee,&p,&n,&m);
    int x,y;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        Insert(x,y);
        Insert(y,x);
    }
    bfs(1,a);
    bfs(2,b);
    bfs(n,c);
    for(int i=1;i<=n;i++){
        ans=min(ans,1LL*(bb*a[i]+ee*b[i]+p*c[i]));
    }
    cout<<ans;
}