#include  < iostream >
#include 
< cmath >
#include 
< limits >

struct  Point
{
    
int  x,y;
}
;

double  graph[ 201 ][ 201 ];
Point   data[
201 ];
int      n;
bool     visite[ 201 ];
double   result[ 201 ];

double  Distance( Point &  a, Point &  b )
{
    
return  sqrt( ( double )( (a.x -  b.x) *  (a.x -  b.x ) +  (a.y -  b.y ) *  (a.y -  b.y ) ) );
}


void  shortpath(  int  t )
{
    
for  (  int  i =   1 ; i <=  n;  ++ i )
    
{
        visite[i]
=   false ;
        result[i]
=   0.0 ;
    }


    
for  (  int  i =   1 ; i <=  n;  ++ i )
        result[i]
=  graph[t][i];

    visite[t]
=   true ;
    
for  (  int  i =   1 ; i <=  n -   1 ++ i )
    
{
        
double  min =  std::numeric_limits < double > ::max();

        
int  k =   - 1 ;
        
for  (  int  j =   1 ; j <=  n;  ++ j )
            
if  (  ! visite[j]  &&  result[j] <  min )
            
{
                min
=  result[j];
                k
=  j;
            }


        visite[k]
=   true ;
        
for  (  int  j =   1 ; j <=  n;  ++ j )
            
if  (  ! visite[j]  &&  std::max( graph[k][j], result[k] ) <  result[j] )
                result[j]
=  std::max( graph[k][j], result[k] );
    }

}


int  main()
{
    
int  num =   1 ;
    
while ( scanf( " %d " , & n), n !=   0  )
    
{
        
for  (  int  i =   1 ; i <=  n;  ++ i )
            scanf(
" %d%d " & data[i].x,  & data[i].y );

        
for  (  int  i =   1 ; i <=  n;  ++ i )
            
for  (  int  j =   1 ; j <=  n;  ++ j )
                graph[i][j]
=  Distance( data[i], data[j] );

        shortpath(
1 );
        printf(
" Scenario #%d\n " , num ++  );
        printf(
" Frog Distance = %.3lf\n " , result[ 2 ] );
        printf(
" \n " );
    }


    
return   0 ;
}
posted on 2008-10-02 15:24 Darren 阅读(220) 评论(0)  编辑 收藏 引用 所属分类: 图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理