POJ 3615 Cow Hurdles：Floyd 求最小最大跳躍高度

題目轉述

有 N 個站點（N ≤ 300），M 條有向路徑（M ≤ 25000），每條路徑有一個欄桿高度 H。牛從 A 跳到 B，只關心路徑上最高欄桿的高度。對 T 個查詢（T ≤ 40000），輸出能到達時的最小可能最大高度，不可達輸出 -1。

模型轉化

路徑的「長度」定義為經過邊的最大高度。任意兩點間的最短路徑即為「最小化路徑上最大邊權」。這是經典的 最小瓶頸路徑 問題，可用 Floyd-Warshall 變體解決。

狀態轉移方程

dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]))

初始 `dist[i][j]` 為直連邊的高度，無邊設 INF，`dist[i][i]=0`。三重循環 k,i,j 更新後，`dist[i][j]` 即為答案。

正確性證明

Floyd 核心是動態規劃：允許中間點編號 ≤ k 時的最優解。對於瓶頸問題，路徑代價為邊權最大值，合併兩段路徑代價取 max，取兩條路徑中較小者即 min。此運算滿足結合律與單調性，故 Floyd 正確。

複雜度

時間 O(N³) = 27×10⁶，空間 O(N²) = 9×10⁴，完全在限制內（1s/64MB）。

代碼要點

• 讀入多組測試直到 EOF。
• 邊可能重複，取最小高度。
• 查詢時若 `dist[A][B] == INF` 輸出 -1。

總結

本題展示了 Floyd 算法在非加法路徑代價（如最大值、最小值、乘積）上的通用擴展能力，只需將 +/min 替換為 max/min 即可。