UVA 10803 Thunder Mountain：Floyd 求最短路最大值

UVA 10803 Thunder Mountain：Floyd 求最短路最大值

n ≤ 100 個城鎮，坐標 (x,y)。距離 ≤ 10km 有路相連，權重為歐氏距離。求任意兩鎮間最短路的最大值（直徑）。若不連通輸出 "Send Kurdy"。

算法流程

1. 讀入座標，計算兩兩距離 dist(i,j)。
2. 初始化鄰接矩陣：d[i][j] = (dist≤10) ? dist : INF，對角線 0。
3. Floyd 三重循環更新最短路：d[i][j] = min(d[i][j], d[i][k]+d[k][j])。
4. 掃描 d[i][j] 找最大值 ans。
5. 若 ans == INF 輸出 "Send Kurdy"，否則 printf("%.4lf", ans)。

代碼關鍵點

double disc(node p1, node p2) {
    return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
}
void floyd() {
    for (k=0; k
複雜度

時間：O(n³) = 1e6，極快。
空間：O(n²)。

注意事項

雙重循環變量命名避免衝突（代碼中外層 k, 中層 i, 內層 j）。
輸出格式：Case #x: 後換行，答案或 "Send Kurdy" 再換行，每用例結束空行。
浮點比較用 ans == INF（INF 取大整數如 1e9）。

裸 Floyd 題，考察圖建模、最短路直徑計算與輸出格式控制。