题目链接：https://vjudge.net/contest/66569#problem/B
题目：
2 0 0 3 4 3 17 4 19 4 18 5 0Sample Output
Scenario #1 Frog Distance = 5.000 Scenario #2 Frog Distance = 1.414
题意：有两只青蛙和若干块石头，现在已知这些东西的坐标，两只青蛙A坐标和青蛙B坐标是第一个和第二个坐标，
现在A青蛙想要到B青蛙那里去，并且A青蛙可以借助任意石头的跳跃，而从A到B有若干通路，
问从A到B的所有通路上的最大边，比如有 有两条通路 1(4)5 (3）2 代表1到5之间的边为4, 5到2之间的边为3，那么该条通路跳跃范围（两块石头之间的最大距离）为 4，
另一条通路 1(6) 4(1) 2 ，该条通路的跳跃范围为6， 两条通路的跳跃范围分别是 4 ，6，我们要求的就是最小的那一个跳跃范围，即4,用三种方法都能解决
思路：最短路模板题，稍微变化一下，就是每条路径选取最大的，选取这几条路径中最小的，即把模板中d[i]>d[now]+lu[now][i]改成d[i]>max(d[now],lu[now][i])就行了，
WA了很多遍由于初始化的原因，以后初始化还是尽量用循环初始化吧，spfa算法代码如下：
// // Created by hanyu on 2019/7/14. // #include<iostream> #include<algorithm> #include<queue> #include<map> #include<cstring> #include<cstdio> #include<math.h> using namespace std; typedef long long ll; #define MAX 0x3f3f3f3f const int maxn=1005; double d[maxn]; double lu[maxn][maxn]; bool book[maxn]; int n; void spfa(int a) { for(int i=2;i<=n;i++){ d[i]=MAX; book[i]=false; } //memset(book,false,sizeof(book)) //memset(d,MAX,sizeof(d)) //别用以上注释用的初始化，就因为这个WA了很多遍，找了两个小时的错误 queue<int>qu; d[a]=false; book[a]=true; qu.push(a); int now; while(!qu.empty()) { now=qu.front(); qu.pop(); book[now]=false; for(int i=1;i<=n;i++) { if(d[i]>max(d[now],lu[now][i])) { d[i]=max(d[now],lu[now][i]); if(!book[i]) { qu.push(i); book[i]=true; } } } } } int main() { int k=0; int a[maxn],b[maxn]; while(~scanf("%d",&n)) { if (n == 0) break; for (int i = 1; i <= n; i++) { scanf("%d%d", &a[i], &b[i]); } for (int i = 1; i <= n; i++){ for (int j = 1; j <= i; j++) { lu[i][j] = lu[j][i] = sqrt(double(a[i] - a[j]) * (a[i] - a[j]) +double(b[i] - b[j]) * (b[i] - b[j])); } } spfa(1); k++; printf("Scenario #%d\n",k); printf("Frog Distance = %.3lf\n\n",d[2]); } return 0; }
[kuangbin带你飞]专题四 最短路练习 B（ POJ 2253） Frogger（spfa）
原文：https://www.cnblogs.com/Vampire6/p/11202573.html