Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 72072 Accepted: 22081
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.
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
题目大意：青蛙a想去青蛙b那里，但是青蛙a所在的位置跳不到青蛙b那里去，所以青蛙a需要借助其他石头做踏板跳过去，要你求在做踏板到达青蛙b那里的这条踏板路径中两座石头最大的距离是多少？（落下了英语差的眼泪，看了半天还没看懂题意），题目默认给定的石头都是有直接路径可达的，类似完全图。
代码：
#include<iostream>
#include<cmath>
#include<stdio.h>
#include<string.h>
#define INF 0x3f3f3f3f
using namespace std;
double dis[205];
int vis[205];
double a[205][205];
int n;
int x[205],y[205];
void dij(int begin){
memset(vis,0,sizeof(vis));//是文件输入，记得每次把vis数组清零，由于这个wa了几发
for(int i=1;i<=n;i++){
dis[i]=a[begin][i];
}
dis[begin]=0;
vis[begin]=1;
for(int i=1;i<=n-1;i++){
double MIN=INF;
for(int j=1;j<=n;j++){
if(!vis[j]&&MIN>dis[j]){
MIN=dis[j];
begin=j;
}
}
vis[begin]=1;
for(int j=1;j<=n;j++){
dis[j]=min(dis[j],max(a[begin][j],dis[begin]));
}
}
}
int main()
{
int pq=1;
while(cin>>n&&n!=0){
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
a[i][j]=a[j][i]=sqrt((double)(((x[i]-x[j])*(x[i]-x[j]))+((y[i]-y[j])*(y[i]-y[j]))));
}
}
dij(1);
cout<<"Scenario #"<<pq++<<endl;
printf("Frog Distance = %.3f\n\n",dis[2]);
}
}
京公网安备 11010502036488号