#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 ;
}
用 dijstla 算法