题解：P14318 「ALFR Round 11」B 行走 (walk)

Wyh_dailyAC · 2025-12-14 16:36:37 · 题解

思路

本题不难，主要在代码。

由于走过一条边权值就变回 1，所以每条边的附加权值只能为一人使用一次，要想再使用就必须重新加。

那么可以将附加权值看作削了一个人的最短路上的一条边。

一股脑加一条边上好，还是均摊着加好？显然是均摊着加好（读者自证）。

所以直接按此贪心策略作答即可。

Code

::::info[Code]

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define int long long

vector<int> E[N];

struct nd {
    int u, s;
    nd(long long _u = 0, long long _s = 0): u(_u), s(_s) {}
};

void solve() {
    int n, m, k; cin >> n >> m >> k;
    for (int i = 1, u, v; i <= m; ++i) {
        cin >> u >> v;
        E[u].emplace_back(v), E[v].emplace_back(u);
    }
    int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    vector<int> vis(n + 5);
    queue<nd> q;
    q.emplace(x1, 0);
    nd ans1 = {y1, -0x3f};
    while (!q.empty()) {
        auto [u, s] = q.front(); q.pop();
        if (u == y1) {
            ans1 = {u, s};
            break;
        }
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto v : E[u]) {
            q.emplace(v, s + 1);
        }
    }
    while (!q.empty()) q.pop();
    fill(vis.begin(), vis.end(), 0);
    q.emplace(x2, 0);
    nd ans2 = {y2, -0x3f};
    while (!q.empty()) {
        auto [u, s] = q.front(); q.pop();
        if (u == y2) {
            ans2 = {u, s};
            break;
        }
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto v : E[u]) {
            q.emplace(v, s + 1);
        }
    }
    if (ans1.s == -0x3f || ans2.s == -0x3f) {
        cout << "-1\n";
        for (int i = 1; i <= n; ++i) E[i].clear();
        return;
    }
    int ans = ans1.s + ans2.s;
    if (k == 0 || ans == 0) {
        cout << ans << "\n";
        for (int i = 1; i <= n; ++i) E[i].clear();
        return;
    }
    if (ans >= k) {
        int tmp = ans - k;
        long double fans = (long double) 1.0 * k / 2.0;
        fans += (long double) 1.0 * tmp;
        cout << fixed << setprecision(15) << fans << "\n";
    } else {
        int ttmp = k / ans;
        int tmp = ans - k % ans;
        long double fans = (long double) 1.0 * tmp / (1.0 + ttmp);
        fans += (long double) 1.0 * (k % ans) / (2.0 + ttmp);
        cout << fixed << setprecision(15) << fans << "\n";
    }
    for (int i = 1; i <= n; ++i) E[i].clear();
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
}

::::