题目描述
Bessie 和 Elsie在不同的区域放牧，他们希望花费最小的能量返回谷仓。从一个区域走到一个相连区域，Bessie要花费B单位的能量，Elsie要花费E单位的能量。
如果某次他们两走到同一个区域，Bessie 可以背着 Elsie走路，花费P单位的能量走到另外一个相连的区域，满足P<B+E。
相遇后，他们可以一直背着走，也可以独立分开。
输入输出样例
输入样例#1：
4 4 5 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8
输出样例#1：
22
3次SPFA就可以了
可以知道，他们在相遇后就不分开了，因为背到终点一定最优
dist1[x]表示从1出发到x最短路
dist2同理
dist3表示到n的最短路
ans=min(dist1[x]*b+dist2[x]*e+dist3[x]*p)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Messi
{
int next,to;
}edge[];
int head[],num,n,m,f[][],ans,dist[],vis[];
void add(int u,int v)
{
num++;
edge[num].next=head[u];
head[u]=num;
edge[num].to=v;
}
void bfs(int x)
{int q[]={},h,t,u,v,i;
q[]=x;h=;t=;
while (h<t)
{
h++;
u=q[h];
vis[u]=;
for (i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if (dist[u]+<dist[v])
{
dist[v]=dist[u]+;
if (vis[v]==)
t++,q[t]=v;
}
}
}
// cout<<x<<' ';
// for (i=1;i<=n;i++)
// cout<<dist[i]<<' ';
// cout<<endl;
}
int main()
{int b,e,p,i,u,v;
cin>>b>>e>>p>>n>>m;
for (i=;i<=m;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
memset(dist,/,sizeof(dist));dist[]=;memset(vis,,sizeof(vis));
bfs();
for (i=;i<=n;i++)
f[i][]=dist[i];
memset(dist,/,sizeof(dist));dist[]=;memset(vis,,sizeof(vis));
bfs();
for (i=;i<=n;i++)
f[i][]=dist[i];
memset(dist,/,sizeof(dist));dist[n]=;memset(vis,,sizeof(vis));
bfs(n);
for (i=;i<=n;i++)
f[i][]=dist[i];
ans=2e9;
for (i=;i<=n;i++)
ans=min(ans,f[i][]*b+f[i][]*e+f[i][]*p);
cout<<ans;
}