学步园

题意是Freddy Frog 要到 Fiona Frog 的石头上去，现在有些石头可以利用 ，Freddy Frog可以跳跃到这些石头上去，求其跳跃得最小距离。

算法：

1.求最短路再取其最长得一条边这样的算法时错得，求出来来得不是其跳跃最小距离。

2. 正确的做法应该是枚举每一条边， 可以二分枚举，边得长度，即跳跃的距离是线性递增得。。。再带限制条件即每条边的大小要小于等于当前枚举得这条边，求其最短路

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
using namespace std;

const int inf = 0x7f7f7f7f;
double mp[310][310];
int xx[310], yy[310], visit[330];
int N;
double dis[310];
double array[400100];

int dij(double x)
{
  for( int i = 1; i <= N; i++)
  {
     dis[i] = inf;
     visit[i] = 0;
  }
  dis[1] = 0;
  for( int i = 1; i <= N; i++)
  {
     int oo = inf, k = 0;
     for( int j = 1; j <= N; j++)
     {
        if( !visit[j] && dis[j] < oo )
        {
              k = j;
              oo = dis[j];

        }

     }
     visit[k] = 1;
     for( int j = 1; j <= N; j++)
     {
        if( !visit[j] && dis[j] > dis[k] + mp[k][j] && mp[k][j] != inf && dis[k] != inf && mp[k][j] <= x)
           dis[j] = dis[k] + mp[k][j];

     }

  }
  if( dis[2] != inf )
     return 1;
  return 0;
}


double search(int l, int r)
{
  int mid, ans = r;
  while( l <= r )
  {
     mid = (l + r)/2;
     if( dij( array[mid] ) )
      { 
        ans = mid;
    r = mid - 1;
      }
     else
    l = mid + 1;
  }
  return array[ans];
}

int main( )
{
  int t = 1;
  while ( scanf("%d",&N), N)
  {
    int n = 0;
    for( int i = 1; i <= N; i++)
      scanf("%d%d",&xx[i],&yy[i]);     
    for( int i = 0; i <= N; i++)
       for( int j = 0; j <= N; j++)
             mp[i][j] = ( i == j ) ? 0 : inf;
    for( int i = 1; i <= N; i++)
    {
       for(int j = i + 1; j <= N; j++)
       {
          double dis = sqrt( (xx[i] - xx[j]) * (xx[i] - xx[j]) + ( yy[i] - yy[j]) *( yy[i] - yy[j]));
          mp[i][j] = mp[j][i] = dis;
          array[n++] = dis;
       }
    }
    printf("Scenario #%d\n",t++);
    sort(array, array + n);
    n = unique(array, array + n) - array;
    printf("Frog Distance = %.3f\n",search(0,n));
    puts("");
  }
  return 0;
}