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

zhangxiaoyu008 · 2025-10-26 22:20:07 · 题解

首先判掉小 A 或小 B 走无法到达目标地点的情况。

显然，小 A 和小 B 走到目标地点的边数一定可以最小化，否则一定可以造出相对应的边数最小的不更劣的方案。

然后这个题就变成了一道数学题。

记小 A 和小 B 走到目标地点的边数为总和的最小值为 n。

那么这道题相当于给定 x_1 + x_2 + \ldots + x_n = k，求 \displaystyle (\sum_{i = 1}^n \frac{1}{1 + x_i})_{\displaystyle \min}。

考虑到如果有还可以更接近的两项及即 x_i - x_j \ge 2，则 \displaystyle \frac{1}{1 + x_i} + \frac{1}{1 + x_j} > \frac{1}{1 + (x_i - 1)} + \frac{1}{1 + (x_j + 1)}（读者自证）。

所以可以得到一定是 x 中的数一定若干个差距 \le 1 的数。

:::info[\large{\mathbf{Code}}]{open}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int T, n, m, s, t, x, y, dist[N];
ll k;
vector<int> g[N];
queue<int> q;
int get(int s, int t) {
    memset(dist, -1, sizeof dist);
    dist[s] = 0;
    q.push(s);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(int v : g[u])
            if(!~dist[v]) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
    }
    return dist[t];
}
int main()
{
    scanf("%d", &T);
    while(T --) {
        scanf("%d%d%lld", &n, &m, &k);
        for(int i = 1; i <= n; i ++) g[i].clear();
        while(m --) {
            scanf("%d%d", &x, &y);
            g[x].push_back(y), g[y].push_back(x);
        }
        scanf("%d%d%d%d", &s, &t, &x, &y);
        int a = get(s, t), b = get(x, y);
        if(!~a || !~b) {
            puts("-1");
            continue;
        }
        int v = a + b;
        if(!v) { // Don't forget special case handling here
            puts("0");
            continue;
        }
        int lef = k % v;
        printf("%.12lf\n", lef * 1.0 / (k / v + 2) + (v - lef) * 1.0 / (k / v + 1));
    }
    return 0;
}

:::