Piggy Back
(piggyback.pas/c/cpp)
【问题描述】
Bessie 和她的姐姐
Elsie 在不同的田块吃草，晚上她们都返回牛棚休息。作为聪明的奶牛，她们想设计一个方案使得步行消耗的能量最少。牛，她们想设计一个方案使得步行消耗的能量最少。Bessie
从一个田块到相邻的田块要耗费 B
个单位的能量， Elsie 从一个田块到相邻的田块要耗费要耗费
E 个单位的能量。然而当
Bessie 和 Elsie
处于同一个田块时， Bessie
用背驮着 Elsie 一起走，从一个田块到相邻的田块要耗费起走，从一个田块到相邻的田块要耗费
P 个单位的能量。如果
P 小于 B+E,则被认为是比较适用的；如果适用的；如果
P 非常小，那么最佳的方案就是尽快使得
Bessie 和 Elsie
在某一田块相遇；当然如果然如果
P 非常大， 那么则尽可能使得 Bessie
和 Elsie 分开走。另一方面，她们对“背驮式”很不高兴，她们不明白为什么这种猪用来驮运的方式会被认为是优秀的方法。给出很不高兴，她们不明白为什么这种猪用来驮运的方式会被认为是优秀的方法。给出
B,E 和 P,帮助她们姐俩找出从牧场到牛棚的花费能量最小的方案。
【输入格式】
第一行包含 5 个正整数
B,E,P,N 和
M。 N
是牧场中田块的数量(分别编号为
1..N),M 表示田块之间通路条数
田块之间通路条数.Bessie
和 Elsie 一开始分别位于
1 和 2,牛棚位于
N.接下来 M
行，每行一对整数 U
和 V，分别表示两个田块之间有通路。通路连接是双向的，可以从的，可以从
1 到 N，和从
2 到 N，并且沿途有一系列通路。
【输出格式】
输出共一行一个整数，表示从牧场到牛棚的花费能量最小的方案。
【输入样例】
4 4 5 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8
【输出样例】
22
【样例解释】
样例中， Bessie
从 1 到
4， Elsie
从 2 到
3 到 4.然后她们一起从
4 到 7
到 8.
【数据规模】
对于 40%的数据：
3≤N,M≤6,000；
对于 100%的数据：
3≤B,E,P,N,M≤40,000；
1≤U，
V≤N；且
U≠V；
第一次见到这题时，都会有一种错觉，认为它需要求出1和2点的最短路径，贪心求最优值，其实不必也不需要这么麻烦，仔细看题目，其实可以发现，背驮式其实是一个关键。我们需要知道Bessie 和 Elsie在哪汇聚，所以我们枚举汇聚点，那问题又来了，如何求汇聚于枚举的点的最短路径呢？SPFA就好了。
code：
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
#define C c = tc ( )
using namespace std; inline char tc(){
static char fl[],*A,*B;
return A==B&&(B=(A=fl)+fread(fl,,,stdin),A==B)?EOF:*A++;
} inline void read(int &x){
static char c;
while(!isdigit(C));x=c-'';
while(isdigit(C))x=x*+c-'';
} struct node{int y,c;};
int B,E,P,n,m,p[][],l[],h,t,vis[],dist[][],ans=2e9;
vector <node> a[]; void spfa1(){
h=t=;
memset(vis,,sizeof(vis));
l[++t]=;
dist[][]=;
while(h<t){
int front=l[++h];vis[front]=;
for(int i=;i<a[front].size();i++){
int to=a[front][i].y;
if(dist[front][]+B<dist[to][]){
dist[to][]=dist[front][]+B;
if(!vis[to])vis[to]=,l[++t]=to;
}
}
}
} void spfa2(){
h=t=;
memset(vis,,sizeof(vis));
l[++t]=;
dist[][]=;
while(h<t){
int front=l[++h];vis[front]=;
for(int i=;i<a[front].size();i++){
int to=a[front][i].y;
if(dist[front][]+E<dist[to][]){
dist[to][]=dist[front][]+E;
if(!vis[to])vis[to]=,l[++t]=to;
}
}
}
} void spfa3(){
h=t=;
memset(vis,,sizeof(vis));
l[++t]=n;
dist[n][]=;
while(h<t){
int front=l[++h];vis[front]=;
for(int i=;i<a[front].size();i++){
int to=a[front][i].y;
if(dist[front][]+P<dist[to][]){
dist[to][]=dist[front][]+P;
if(!vis[to])vis[to]=,l[++t]=to;
}
}
}
} int main(){ freopen("piggyback.in","r",stdin);
freopen("piggyback.out","w",stdout); read(B),read(E),read(P),read(n),read(m);
for(int i=;i<=m;i++){
read(p[i][]),read(p[i][]);
a[p[i][]].push_back((node){p[i][],});
a[p[i][]].push_back((node){p[i][],});
}
memset(dist,,sizeof(dist));
spfa1();spfa2();spfa3();
for(int i=;i<=n;i++){
ans=min(ans,dist[i][]+dist[i][]+dist[i][]);
}
printf("%d",ans);
fclose(stdin),fclose(stdout);
return ;
}