misschuer

常用鏈接

統(tǒng)計(jì)

隨筆 - 61
文章 - 1
評(píng)論 - 18
引用 - 0

積分與排名

積分 - 24928
排名 - 727

百事通

hao123
WPL
杭電
松松
星和

一個(gè)人的旅行

#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 此最相思閱讀(142) 評(píng)論(0) 編輯收藏引用

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

misschuer

導(dǎo)航

公告

留言簿

隨筆分類

文章分類

隨筆檔案

文章檔案

閱讀排行榜

評(píng)論排行榜

常用鏈接

統(tǒng)計(jì)

積分與排名

百事通

最新評(píng)論

一個(gè)人的旅行