杂题——公园

公园

今天是六一节，小度去公园玩，公园一共 N 个景点，正巧看到朋友圈度度熊也在这个公园玩，于是他们约定好一块去景点 N。 小度当前所在景点编号为 T，从一个景点到附近的景点需要消耗的体力是 TE，而度度熊所在景点编号为 F ，移动消耗为 FE。 好朋友在一块，赶路都会开心很多，所以如果小度和度度熊一块移动(即在相同位置向相同方向移动)，每一步他俩的总消耗将会减少 S。
求他俩到景点 N 时，所需要的总消耗最少是多少？

格式

输入格式：

第一行三个数值，TE,FE,S ，分别代表小度移动消耗值，度度熊移动消耗值，一起移动的消耗减少值。1≤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

输入：

1
2
3
4
5
6
7
8
9
10
4 4 3
1 2 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8

输出：

1
22

思路

​ 这道题目是一道非常简单的BFS类的题目，基本思路就是分别求出小度、度度熊到每个结点位置还有小度和度度熊同时到达某个位置然后一起出发到N的最小消耗体力，然后我们求最小体力这样求就ok了：res=min(res, A[i], B[i], C[i]);

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;
const int N = 4e4 + 10;
const long long INF = 2e9;
int k1, k2, k3, a, b, n, m;
vector<int> p[N];
long long A[N], B[N], C[N];
int cnt[N];
bool st[N];

void bfs(int start, long long dist[], int k){
    for (int i = 1; i <= n; i++) dist[i] = INF;
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    while (q.size()) {
        int t = q.front();
        q.pop();
        for (auto kk : p[t]) {
            if (dist[kk] > dist[t] + k) {
                dist[kk] = dist[t] + k;
                q.push(kk);
            }
        }
    }

}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> k1 >> k2 >> k3 >> a >> b >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        p[x].push_back(y);
        p[y].push_back(x);
    }

    bfs(a, A, k1);
    bfs(b, B, k2);

    // cout << A[2] << '\n';
    if (A[n] == INF || B[n] == INF) {
        cout << -1;
        return 0;
    }
    
    bfs(n, C, k1 + k2 - k3);

    long long res = INF;
    for (int i = 1; i <= n; i++) {
        if (A[i] != INF && B[i] != INF && C[i] != INF) {
            res = min(res, A[i] + B[i] + C[i]);
        }
    }

    cout << res;
    return 0;
}