解题思路

这道题的关键是找到从 Freddy 的石头（起点） 到 Fiona 的石头（终点） 的路径，使得这条路径上的 最大跳跃距离最小。这类似于 最小化路径中的最大边权 问题，可以使用 Dijkstra 算法的变种 或 Kruskal 算法（最小生成树） 来解决。

方法 ：Dijkstra 算法的变种（优先队列优化）

• 核心思想：修改 Dijkstra 算法，使其不再计算路径总长度，而是记录 路径上的最大跳跃距离，并优先选择 最大跳跃距离最小 的路径。
• 步骤：
  1. 计算所有石头之间的欧几里得距离，构建邻接表或邻接矩阵。
  2. 使用优先队列（最小堆），存储 (当前路径的最大跳跃距离, 当前石头)。
  3. 每次从堆顶取出 当前最大跳跃距离最小 的路径，并尝试更新其邻接点的最大跳跃距离。
  4. 当终点被访问时，返回其最大跳跃距离。

C++ 代码实现（Dijkstra 变种）

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <iomanip>
using namespace std;

typedef pair<double, int> pdi; // {max_jump, stone_index}

double calculateDistance(int x1, int y1, int x2, int y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

double frogDistance(vector<pair<int, int> >& stones) {
    int n = stones.size();
    vector<double> maxJump(n, 1e9); // 记录到每个石头的路径上的最大跳跃距离
    priority_queue<pdi, vector<pdi>, greater<pdi> > pq; // 最小堆

    maxJump[0] = 0; // 起点是 stones[0]
    pq.push({0, 0});

    while (!pq.empty()) {
        double currentMax = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (u == 1) break; // 到达终点 stones[1]

        for (int v = 0; v < n; ++v) {
            if (u == v) continue;
            double jump = calculateDistance(stones[u].first, stones[u].second, stones[v].first, stones[v].second);
            double newMax = max(currentMax, jump);
            if (newMax < maxJump[v]) {
                maxJump[v] = newMax;
                pq.push({newMax, v});
            }
        }
    }
    return maxJump[1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, caseNum = 1;
    while (cin >> n, n != 0) {
        vector<pair<int, int> > stones(n);
        for (int i = 0; i < n; ++i) {
            cin >> stones[i].first >> stones[i].second;
        }

        double distance = frogDistance(stones);
        cout << "Scenario #" << caseNum++ << "\n";
        cout << "Frog Distance = " << fixed << setprecision(3) << distance << "\n\n";
    }
    return 0;
}