misschuer

常用链接

统计

积分与排名

百事通

最新评论

一个人的旅行

#include<iostream>

using namespace std ;

#define N 1001

#define MAX 10000

int dist [ N ] ;

bool flag [ N ] ;

int v [ N ] [ N ] ;

int number ;

int mindist ()
{

      int index = -1 ;
      
      int i , j ;
      
      for ( i = 1 ; i <= number ; ++ i )
      
        if ( flag [ i ] )
        {
        
          index = i ;
          
          break ;
          
        }
        
      for ( j = i + 1 ; j <= number ; ++ j )
      
        if( dist [ index ] > dist [ j ] && flag [ j ] )
        
            index = j ;

      return index ;
      
}

int main ()
{
    int t , s , d ;
    
    int a , b , time ;
    
    int i , j , k ;
    
    int city ;
    
    int min ;
    
    int want ;

    for ( i = 1 ; i <= 1000 ; ++i )
    
        for ( j = 1 ; j <= 1000 ; ++ j )
        { 
        
            v [ i ] [ j ] = v [ j ] [ i ] = MAX ;
            
        }
        
        dist [ 0 ] = 0 ;

    while ( scanf( "%d%d%d" , & t , & s , & d ) != EOF )
    {

            number = 0 ;
            
            for ( i = 1 ; i <= t ; ++ i )
            {

                scanf ( "%d%d%d" , & a , & b , & time ) ;
                
                if ( v [ a ] [ b ] > time )
                
                  v [ b ] [ a ] = v [ a ] [ b ] = time ;
                  
                if ( number < b )
                
                number = b ;
                
                if( number < a )
                
                 number = a ;
                
                }

            for ( i = 1 ; i <= number ; ++ i )
            
                flag [ i ] = true ;

            for ( i = 1 ; i <= s ; ++ i )
            {

                scanf ( "%d" , & city ) ;

                v [ city ] [ 1 ] = 0 ;
                
            }

            

            j = 1 ;
            k = 0 ;
            while ( j )
            {

                if ( k != -1 )
                {

                    for ( i = 1 ;i <= number ; ++ i )
                    {

                        if ( k == 0 )
                        
                            dist [ i ] = v [ i ] [ 1 ] ;
                            
                        else
                        {
                        
                           if( dist [ i ] > v [ i ] [ k ] + dist [ k ] )
                           
                               dist [ i ] = v [ i ] [ k ] + dist [ k ] ;
                        }
                        
                    }
                    
                    flag [ k ] = false ;
                    
                }
                
                else 
                
                    break ;

                 k = mindist () ;
                 
            }
  
           scanf ( "%d" , & want ) ;
           
            min = dist [ want ] ;
            
            for ( i = 2 ; i <= d ; ++ i )
            {

                scanf ( "%d" , & want ) ;
                
                if ( min > dist [ want ] )
                
                    min = dist [ want ] ;
                    
            }
            
            printf ( "%d\n" , min ) ;

            for ( i = 1 ; i <= number ; ++ i )
            
                for ( j = i ; j <= number ; ++ j )
                
                    v [ i ] [ j ] = v [ j ] [ i ] = MAX ;
                    
    }
    
    return 23 ;
    
}

posted on 2009-04-18 10:44 此最相思 阅读(136) 评论(0)  编辑 收藏 引用


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