今天是六一节，小度去公园玩，公园一共 N 个景点，正巧看到朋友圈度度熊也在这个公园玩，于是他们约定好一块去景点 N。 小度当前所在景点编号为 T，从一个景点到附近的景点需要消耗的体力是 TE，而度度熊所在景点编号为 F ，移动消耗为 FE。 好朋友在一块，赶路都会开心很多，所以如果小度和度度熊一块移动(即在相同位置向相同方向移动)，每一步他俩的总消耗将会减少 S。
求他俩到景点 N 时，所需要的总消耗最少是多少？
格式
输入格式：
第一行三个数值，TE,FE,S ，分别代表小度移动消耗值，度度熊移动消耗值，一起移动的消耗减少值。1≤TE,FE,S≤40000,S≤TE+FE1≤TE,FE,S≤40000,S≤TE+FE；
第二行四个数值，T,F,N,M ，分别代表小度出发点，度度熊出发点，目标节点，总路径数。1≤T,F,N,M≤40000；
接下来M 行，每行两个整数 X,Y，代表连通的两个景点。1≤X,Y≤N。
输出格式：
一个整数，即总消耗最小值。如果不能到达 N ， 输出-1。
样例 1
输入：
4 4 3
1 2 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8
输出：22
#include<bits/stdc++.h> using namespace std; int te,fe,s; int t,f,n,m; const int maxn=40005; vector<int> v[maxn]; int p1[maxn],p2[maxn],d[maxn]; void bfs(int start,int val[]){ for(int i=1;i<=n;i++) val[i]=n+1; queue<int> Q; Q.push(start); val[start]=0; while(!Q.empty()){ int cur=Q.front(); Q.pop(); for(int i=0;i<v[cur].size();i++){ int d=v[cur][i]; if(val[d]>val[cur]+1){ Q.push(d); val[d]=val[cur]+1; } } } } int main( ) { scanf("%d %d %d",&te,&fe,&s); scanf("%d %d %d %d",&t,&f,&n,&m); for(int i=0;i<m;i++){ int a,b; scanf("%d %d",&a,&b); v[a].push_back(b); v[b].push_back(a); } bfs(t,p1); bfs(f,p2); bfs(n,d); if(p1[n]==n+1||p2[n]==n+1){ printf("-1"); }else{ int res=p1[n]*te+p2[n]*fe; for(int i=1;i<n;i++){ int cur=p1[i]*te+p2[i]*fe+d[i]*(te+fe-s); res=min(res,cur); } printf("%d",res); } return 0; }
