zoj 1942 Frogger

#include <iostream>#include <cstdio>#include <string.h>#include <math.h>#define MAX 2000000000#define eps 1e-9using namespace std;struct point{    double x,y;}p[205];double map[1010][1010],dis[1010];bool flag[1010];int dbcmp( double a ){    if( fabs(a)<eps )  return 0;    return a>0?1:-1;}double dijkstra( int sta,int n ){    int i,j,mark;    double mini;    memset( flag,0,sizeof(flag) );    memset( dis,0,sizeof(dis) );    flag[sta]=1;    for( j=1;j<n;j++ )    {        mini=MAX;        for( i=0;i<n;i++ )        { if( !flag[i] ) {     if( dbcmp( map[sta][i] )!=0 )     {         if( dbcmp( dis[i] )==0 )   dis[i]=map[sta][i];         else if( dbcmp( dis[i]-max( dis[sta],map[sta][i] ) )==1 )  dis[i]=max( dis[sta],map[sta][i] );     }     if( dbcmp( mini-dis[i] )==1 && dbcmp( dis[i] )!=0 )     {         mini=dis[i];         mark=i;     } }        }        if( dbcmp( mini-MAX )==0 ) break;        sta=mark;        flag[sta]=1;    }    return dis[1];}int main(){    int n,i,j,co;    double temp;    co=1;    while( scanf( "%d",&n ) && n )    {        for( i=0;i<n;i++ ) scanf( "%lf%lf",&p[i].x,&p[i].y );        memset( map,0,sizeof(map) );        for( i=0;i<n;i++ ) for( j=i+1;j<n;j++ ) {     temp=sqrt( pow( p[i].x-p[j].x,2 )+pow( p[i].y-p[j].y,2 ) );     map[i][j]=temp;     map[j][i]=temp; }        printf( "Scenario #%dn",co );        printf( "Frog Distance = %.3lfnn",dijkstra( 0,n ) );        co++;    }    return 0;}