#include  < iostream >
#include 
< algorithm >
#include 
< limits >

int   n,m;
int   graph[ 1001 ][ 1001 ];
bool  visite[ 1001 ];
int   result[ 1001 ];

void  shortpath()
{
    memset( visite, 
false sizeof (visite) );
    memset( result, 
0 sizeof (result) );

    visite[
1 ] =   true ;

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

    
for  (  int  i =   1 ; i <  n;  ++ i )
    
{
        
int  max =   0 ;
        
int  k =   - 1 ;

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


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


}


int  main()
{
    
int  test;
    scanf(
" %d " , & test);

    
for  (  int  t =   1 ; t <=  test;  ++ t )
    
{
        scanf(
" %d%d " , & n, & m);
        memset( graph, 
0 sizeof (graph) );

        
for  (  int  i =   0 ; i <  m;  ++ i )
        
{
            
int  x, y,d;
            scanf(
" %d%d%d " , & x, & y, & d);

            graph[x][y]
=  d;
            graph[y][x]
=  d;
        }


        shortpath();
        printf(
" Scenario #%d:\n " , t );
        printf(
" %d\n " , result[n] );
        printf(
" \n " );
    }


    
return   0 ;
}



posted on 2008-10-02 17:39 Darren 阅读(251) 评论(0)  编辑 收藏 引用 所属分类: 图论

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