POJ 2253 Frogger：Floyd-Warshall 求最小最大邊權路徑（Frog Distance）

問題定義

給定 n ≤ 200 個石頭座標，石頭 1 為起點，石頭 2 為終點。青蛙可跳躍任意兩石頭間，跳躍距離為歐氏距離。
定義路徑的代價為路徑上最長單次跳躍距離。
求從 1 到 2 所有路徑中，代價最小者（即 Minimax 路徑 / Frog Distance）。

Floyd-Warshall 變形

經典 Floyd 求最短路：d[i][j] = min(d[i][j], d[i][k] + d[k][j])
Minimax 版本：d[i][j] = min(d[i][j], max(d[i][k], d[k][j]))
含義：經過 k 的路徑最長邊為兩段最長邊的最大值；取所有中繼點 k 的最小值。

演算法步驟

1. 初始化 d[i][j] 為點 i, j 間歐氏距離。
2. 三重迴圈 k, i, j 執行 d[i][j] = min(d[i][j], max(d[i][k], d[k][j]))。
3. 答案為 d[1][2]（或 d[0][1] 視索引）。

完整 C++ 實作

#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 205;
const double INF = 1e100;

double dist[MAXN][MAXN];
int x[MAXN], y[MAXN];

int main() {
    int n, cas = 0;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &x[i], &y[i]);
            for (int j = 1; j < i; ++j) {
                int dx = x[i] - x[j], dy = y[i] - y[j];
                dist[i][j] = dist[j][i] = sqrt(dx*dx + dy*dy);
            }
            dist[i][i] = 0;
        }

        // Floyd-Warshall Minimax
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]));

        printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++cas, dist[1][2]);
    }
    return 0;
}

替代解法：Dijkstra 變形

將邊權視為「代價」，使用優先隊列，狀態為 (maxEdgeSoFar, node)，每次取出最小 maxEdgeSoFar 的節點擴展。
複雜度 O(E log V) = O(V² log V)，對稠密圖 (V=200) 略慢於 Floyd O(V³) 但同數量級。

關鍵點總結

• Minimax 語義：路徑代價 = 最大邊權，求最小化該最大值。
• Floyd 變形通用性：任何滿足「路徑代價 = 聚合函數(邊權)」且聚合函數可分解為 f(path) = g(f(sub1), f(sub2)) 的問題均可用 Floyd 變形（如最大邊權、最小邊權、乘積等）。
• 輸出格式：Scenario #x、Frog Distance = y.yyy、空行分隔。
• 精度：double 足夠，sqrt 計算距離，%.3f 四捨五入輸出。

樣例驗證

Input:
2
0 0
3 4
3
17 4
19 4
18 5
0

Output:
Scenario #1
Frog Distance = 5.000

Scenario #2
Frog Distance = 1.414