题意：要从起点的石头跳到终点的石头，设The frog distance为从起点到终点的某一路径中两点间距离的最大值，问在从起点到终点的所有路径中The frog distance的最小值为多少。
分析：
解法一:Dijkstra，修改最短路模板，d[u]表示从起点到u的所有路径中两点间距离的最大值的最小值。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define lowbit(x) (x & (-x))
const double eps = 1e-15;
inline int dcmp(double a, double b){
if(fabs(a - b) < eps) return 0;
return a > b ? 1 : -1;
}
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 200 + 10;
const int MAXT = 10000 + 10;
using namespace std;
struct Edge{
int from, to;
double dist;
Edge(int f, int t, double d):from(f), to(t), dist(d){}
};
struct HeapNode{
double d;
int u;
HeapNode(double dd, int uu):d(dd), u(uu){}
bool operator < (const HeapNode& rhs)const{
return d > rhs.d;
}
};
struct Dijkstra{
int n, m;
vector<Edge> edges;
vector<int> G[MAXN];
double d[MAXN];
bool done[MAXN];
void init(int n){
this -> n = n;
for(int i = 0; i <= n; ++i) G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, double dist){
edges.push_back(Edge(from, to, dist));
m = edges.size();
G[from].push_back(m - 1);
}
void dijkstra(int s){
priority_queue<HeapNode> Q;
for(int i = 0; i <= n; ++i){
d[i] = 10000000.0;
}
memset(done, false, sizeof done);
d[s] = 0;
Q.push(HeapNode(0, s));
while(!Q.empty()){
HeapNode x = Q.top();
Q.pop();
int u = x.u;
if(done[u]) continue;
done[u] = true;
for(int i = 0; i < G[u].size(); ++i){
Edge &e = edges[G[u][i]];
double tmp = max(d[u], e.dist);
if(tmp < d[e.to]) {
d[e.to] = tmp;
Q.push(HeapNode(d[e.to], e.to));
}
}
}
}
}dij;
struct Node{
int x, y;
void read(){
scanf("%d%d", &x, &y);
}
}num[MAXN];
double getD(Node& a, Node &b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int main(){
int n;
int kase = 0;
while(scanf("%d", &n) == 1){
if(!n) return 0;
for(int i = 0; i < n; ++i) num[i].read();
dij.init(n);
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
double d = getD(num[i], num[j]);
dij.AddEdge(i, j, d);
dij.AddEdge(j, i, d);
}
}
dij.dijkstra(0);
printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++kase, dij.d[1]);
}
return 0;
}
解法二：flod，pic[i][j]表示从i到j的所有路径中两点间距离的最大值的最小值。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define lowbit(x) (x & (-x))
const double eps = 1e-8;
inline int dcmp(double a, double b){
if(fabs(a - b) < eps) return 0;
return a > b ? 1 : -1;
}
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 200 + 10;
const int MAXT = 10000 + 10;
using namespace std;
double pic[MAXN][MAXN];
struct Node{
int x, y;
void read(){
scanf("%d%d", &x, &y);
}
}num[MAXN];
double getD(Node& a, Node &b){
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int main(){
int n;
int kase = 0;
while(scanf("%d", &n) == 1){
if(!n) return 0;
for(int i = 0; i < n; ++i) num[i].read();
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
double d = getD(num[i], num[j]);
pic[i][j] = pic[j][i] = d;
}
}
for(int k = 0; k < n; ++k){
for(int i = 0; i < n; ++i){
for(int j = i + 1; j < n; ++j){
if(pic[i][k] < pic[i][j] && pic[k][j] < pic[i][j]){
pic[j][i] = pic[i][j] = max(pic[i][k], pic[k][j]);
}
}
}
}
printf("Scenario #%d\nFrog Distance = %.3f\n\n", ++kase, pic[0][1]);
}
return 0;
}