UVa 534 Frogger

题目描述题目要求计算从石头111Freddy\texttt{Freddy}Freddy的石头到石头222Fiona\texttt{Fiona}Fiona的石头的“青蛙距离”。青蛙距离定义为所有可能路径中路径上最长跳跃的最小值即最小化最大边长。这实际上是图论中的“最小瓶颈路径”问题。输入格式输入包含多个测试用例。每个测试用例的第一行是一个整数nnn2≤n≤2002 \le n \le 2002≤n≤200表示石头的数量。接下来nnn行每行两个整数(xi,yi)(x_i, y_i)(xi​,yi​)表示第iii块石头的坐标。石头111是Freddy\texttt{Freddy}Freddy的石头石头222是Fiona\texttt{Fiona}Fiona的石头。每个测试用例后有一个空行。输入以n0n 0n0结束。输出格式对于每个测试用例输出Scenario #x然后输出Frog Distance y其中yyy保留三位小数。每个测试用例输出后跟一个空行。样例输入2 0 0 3 4 3 17 4 19 4 18 5 0输出Scenario #1 Frog Distance 5.000 Scenario #2 Frog Distance 1.414题目分析本题的核心是计算最小瓶颈路径即从源点到目标点的所有路径中路径上最大边权的最小值。Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall变体使用类似Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall的方法dist[i][j]min⁡(dist[i][j],max⁡(dist[i][k],dist[k][j])) dist[i][j] \min(dist[i][j], \max(dist[i][k], dist[k][j]))dist[i][j]min(dist[i][j],max(dist[i][k],dist[k][j]))初始化dist[i][j]dist[i][j]dist[i][j]为iii和jjj之间的欧几里得距离的平方或直接存储距离。最终dist[1][2]dist[1][2]dist[1][2]即为最小瓶颈距离。算法步骤计算所有点对之间的欧几里得距离平方避免开方最后再开方。运行 Floyd-Warshall 变体更新dist[i][j]min⁡(dist[i][j],max⁡(dist[i][k],dist[k][j]))dist[i][j] \min(dist[i][j], \max(dist[i][k], dist[k][j]))dist[i][j]min(dist[i][j],max(dist[i][k],dist[k][j]))。输出dist[1][2]\sqrt{dist[1][2]}dist[1][2]​保留三位小数。复杂度分析n≤200n \le 200n≤200Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法O(n3)8×106O(n^3) 8 \times 10^6O(n3)8×106可接受。代码实现// Frogger// UVa ID: 534// Verdict: Accepted// Submission Date: 2016-08-10// UVa Run Time: 0.010s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn,distances[201][201],cases0;pairint,intpoints[201];while(cinn,n){for(inti1;in;i)cinpoints[i].firstpoints[i].second;for(inti1;in;i)for(intji1;jn;j)distances[i][j]distances[j][i](points[j].first-points[i].first)*(points[j].first-points[i].first)(points[j].second-points[i].second)*(points[j].second-points[i].second);for(intk1;kn;k)for(inti1;in;i)for(intj1;jn;j)distances[i][j]min(distances[i][j],max(distances[i][k],distances[k][j]));coutScenario #cases\n;coutFrog Distance fixedsetprecision(3)sqrt(distances[1][2])\n;cout\n;}return0;}