poj2253

链接:poj2253

Description

  • 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

    题解

  • 最短路变形,松弛及松弛条件改为max(dis[k],g[k][i])<dis[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
typedef pair<double,int> l;
const int N=507;
double g[N][N],dis[N];
int vis[N],x[N],y[N],n,cnt;
priority_queue<l,vector<l>,greater<l> >q;

double len(int a,int b){
return sqrt(pow((double)x[a]-x[b],2)+pow((double)y[a]-y[b],2));
}

double dijkstra(int s,int t){
while(!q.empty())q.pop();
memset(vis,0,sizeof(vis));
rep(i,1,n)dis[i]=0x3f3f3f3f;
q.push(l(dis[s]=0,s));
while(!q.empty()){
int k=q.top().second;
q.pop();
vis[k]=1;
rep(i,1,n)if(max(dis[k],g[k][i])<dis[i]){
dis[i]=max(dis[k],g[k][i]);
if(!vis[i])q.push(l(dis[i],i));
}
}
return dis[t];
}

int main(){
while(~scanf("%d",&n)&&n){
rep(i,1,n)scanf("%d%d",&x[i],&y[i]);
rep(i,1,n)rep(j,1,i-1)g[i][j]=g[j][i]=len(i,j);
printf("Scenario #%d\nFrog Distance = %.3lf\n\n",++cnt,dijkstra(1,2));
}
return 0;
}