526互联

BD202301 公园

发布时间 2023-09-19 11:38:08作者: ysqfirmament

BD202301公园

T和F走到一个汇合点一起走到N

设汇合点为X

则要TX和FX和XN的最短距离

BFS T、F、N到每个点的最短距离

遍历每一个点去寻找X

取答案最小值

ans = min(ans, TX *te + FX * fe + XN * (te + fe - s))

#include<bits/stdc++.h> 

using namespace std;
using ll = long long;

const int N = 40010;

ll te, fe, s;
ll t, f, n, m;
ll ans = 0x3f3f3f3f;
vector<ll> v[N];
ll dis[3][N];

void bfs(ll dist[], ll st) 
{
    for (int i = 1; i <= n; i++) dist[i] = -1;
    queue<ll> q;
    dist[st] = 0;
    q.push(st);
    while (!q.empty()) {
        int head = q.front();
        q.pop();
        for (auto x: v[head]) {
            if (dist[x] == -1) {
                dist[x] = dist[head] + 1;
                q.push(x);
            }
        }
    }
}

int main( )
{
    cin >> te >> fe >> s;
    cin >> t >> f >> n >> m;
    ll tfs = te + fe - s;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    bfs(dis[0], t);
    bfs(dis[1], f);
    bfs(dis[2], n);
    for (int i = 1; i <= n; i++) {
        if (dis[0][i] != -1 && dis[1][i] != -1 && dis[2][i] != -1) {
            ans = min(ans, dis[0][i] *te + dis[1][i] *fe + dis[2][i] * tfs);
        }
    }
    if (ans == 0x3f3f3f3f) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}