撰写
Freddy Frog is sitting on a stone in the middle of a lake. Suddenly he notices Fiona Frog who is sitting on another stone. He plans to visit her, but since the water is dirty and full of tourists’ sunscreen, he wants to avoid swimming and instead reach her by jumping.
Unfortunately Fiona’s stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps.
To execute a given sequence of jumps, a frog’s jump range obviously must be at least as long as the longest jump occuring in the sequence.
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.You are given the coordinates of Freddy’s stone, Fiona’s stone and all other stones in the lake. Your job is to compute the frog distance between Freddy’s and Fiona’s stone.
Unfortunately Fiona’s stone is out of his jump range. Therefore Freddy considers to use other stones as intermediate stops and reach her by a sequence of several small jumps.
To execute a given sequence of jumps, a frog’s jump range obviously must be at least as long as the longest jump occuring in the sequence.
The frog distance (humans also call it minimax distance) between two stones therefore is defined as the minimum necessary jump range over all possible paths between the two stones.You are given the coordinates of Freddy’s stone, Fiona’s stone and all other stones in the lake. Your job is to compute the frog distance between Freddy’s and Fiona’s stone.
Input
The input will contain one or more test cases. The first line of each test case will contain the number of stones n (2<=n<=200). The next n lines each contain two integers xi,yi (0 <= xi,yi <= 1000) representing the coordinates of stone #i. Stone #1 is Freddy’s stone, stone #2 is Fiona’s stone, the other n-2 stones are unoccupied. There’s a blank line following each test case. Input is terminated by a value of zero (0) for n.
Output
For each test case, print a line saying “Scenario #x” and a line saying “Frog Distance = y” where x is replaced by the test case number (they are numbered from 1) and y is replaced by the appropriate real number, printed to three decimals. Put a blank line after each test case, even after the last one.
Sample Input
2 0 0 3 4 3 17 4 19 4 18 5 0
Sample Output
Scenario #1 Frog Distance = 5.000 Scenario #2 Frog Distance = 1.414
题意：有点绕，找出所有路中到最长边的最小值，也就是青蛙一步需要能跳的最大值。
题解：最短路改编，我用的是spfa（但用dijkstra大概会更好，毕竟是稠密图。不过好像又差不多？毕竟标记过了）；将核心语句改为：
if(dist[v]>max(dist[u],E[u][i].cost))//也就是当dist[v]（v之前的边中的最大值）大于u之间边中的最大值与u到v的值的最大值时，更新v点之前答案（可以将每一次的v点看作终点）
{
dist[v]=max(dist[u],E[u][i].cost);
if(!vis[v])
{
vis[v]=true;
que.push(v);
//if(++cnt[v]>n) //cnt[i]为入队列次数，用来判定是否存在负环回路
//return false;
}
}
代码：
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<string,pair<int,int> > pii;
typedef long long ll;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
const int MAXN =205;
struct Edge
{
int v;
double cost;
Edge(int _v=0,double _cost=0.0):v(_v),cost(_cost){}
};
vector<Edge>E[MAXN];
void addedge(int u,int v,double w)
{
E[u].push_back(Edge(v,w));
}
bool vis[MAXN];//在队列标志
int cnt[MAXN];//每个点的入队列次数
double dist[MAXN];
bool SPFA(int start,int n)
{
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)dist[i]=INF*1.0;
vis[start]=true;
dist[start]=0.0;
queue<int>que;
while(!que.empty())que.pop();
que.push(start);
memset(cnt,0,sizeof(cnt));
cnt[start]=1;
while(!que.empty())
{
int u=que.front();
que.pop();
vis[u]=false;
for(int i=0;i<E[u].size();i++)
{
int v=E[u][i].v;
if(dist[v]>max(dist[u],E[u][i].cost))
{
dist[v]=max(dist[u],E[u][i].cost);
if(!vis[v])
{
vis[v]=true;
que.push(v);
if(++cnt[v]>n) //cnt[i]为入队列次数，用来判定是否存在负环回路
return false;
}
}
}
}
return true;
}
struct point{
int x;
int y;
}p[maxn];
int main(){
int n,x,y;
int cnt = 0;
while(~scanf("%d",&n)&&n){
rep(i,1,n)E[i].clear();
scanf("%d%d",&p[1].x,&p[1].y);
scanf("%d%d",&p[n].x,&p[n].y);
rep(i,2,n-1){
scanf("%d%d",&p[i].x,&p[i].y);
}
rep(i,1,n){
rep(j,1,n){
if(i!=j){
addedge(i,j,sqrt((double)((p[i].x-p[j].x)*(p[i].x-p[j].x))+(double)((p[i].y-p[j].y)*(p[i].y-p[j].y)) ) );
}
}
}
SPFA(1,n);
//Scenario #1
//Frog Distance = 5.000
cout<<"Scenario #"<<++cnt<<endl;
cout<<"Frog Distance = ";
printf("%.3f\n\n", dist[n]);
}
return 0;
}