alan23273850 的刷題筆記
c125: 00534 - Frogger
Tags: floyd-warshall, graph
出處：https://zerojudge.tw/ShowProblem?problemid=c125
提交：https://zerojudge.tw/Submissions?problemid=c125&account=allllllan123456
問題：給定 $n\in[2,200]$ 顆湖上石頭的座標 $x_i,\ y_i\in[0,1000]$，請問一隻青蛙要怎麼從第一號石頭跳到第二號石頭才能讓途中遇到最長的一次蛙跳距離最短？
解法：這題的模型其實跟 a674 一模一樣，但是湖上的石頭們彼此之間沒有連不連通的問題，只要是夠強大的青蛙就可以在每顆石頭之間恣意地跳動。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int n, cases=0, x[200], y[200], dist[200][200];
6 while (cin >> n && n) {
7 memset(dist, 0x7f, sizeof dist); // 一個 byte 的最大值
8 for (int i=0; i<n; i++) cin >> x[i] >> y[i];
9 for (int i=0; i<n; i++)
10 for (int j=i; j<n; j++)
11 dist[i][j] = dist[j][i] = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
12 for (int k=0; k<n; k++)
13 for (int i=0; i<n; i++)
14 for (int j=i+1; j<n; j++)
15 dist[j][i] = dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]));
16 cout << "Scenario #" << (++cases) << '\n';
17 cout << "Frog Distance = " << fixed << setprecision(3) << sqrt(dist[0][1]) << "\n\n";
18 }
19 return 0;
20}