Pagini recente » Cod sursa (job #3222234) | Cod sursa (job #1864355) | Cod sursa (job #1763290) | Cod sursa (job #368759) | Cod sursa (job #2937559)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin( "ubuntzei.in" );
ofstream cout( "ubuntzei.out" );
const int INF = 2e9;
const int MAX = 2005;
const int K = 15;
vector<pair <int, int>> g[ MAX ];
long long dp[ 1 << K ][ K ];
int d[ MAX ][ MAX ];
void dijkstra( int s, int n ) {
priority_queue<pair<int, int>> pq;
fill( d[ s ] + 1, d[ s ] + n + 1, INF );
for( pq.emplace( 0, s ), d[ s ][ s ] = 0; !pq.empty(); pq.pop() ) {
int dist = pq.top().first;
int u = pq.top().second;
if( -dist != d[ s ][ u ] )
continue;
pair<int, int> x;
for( auto x : g[ u ] )
if( d[ s ][ x.first ] > x.second - dist ) {
d[ s ][ x.first ] = x.second - dist;
pq.emplace( dist - x.second, x.first );
}
}
}
int main()
{
int n, m, k;
cin >> n >> m >> k;
vector<int> stops( k );
for( int i = 0; i < k; i++ )
cin >> stops[ i ];
for( int i = 0; i < m; i++ ) {
int u, v, w;
cin >> u >> v >> w;
g[ u ].emplace_back( v, w );
g[ v ].emplace_back( u, w );
}
dijkstra( 1, n );
for( int stop : stops )
dijkstra( stop, n );
int kk = 1 << k;
for( int i = 1; i < kk; i++ )
for( int j = 0; j < k; j++ )
dp[ i ][ j ] = INF;
for( int i = 0; i < k; i++ )
dp[ 1 << i ][ i ] = d[ 1 ][ stops[ i ] ];
// sos :)
for( int mask = 1; mask < kk; mask++ ) {
for( int cm = mask; cm; cm &= cm - 1 ) {
int u = 31 - __builtin_clz( cm & ( -cm ) );
for( int v = 0; v < k; v++ )
if( !( mask & ( 1 << v ) ) ) {
int mv = mask ^ ( 1 << v );
dp[ mv ][ v ] = min( dp[ mv ][ v ], dp[ mask ][ u ] + d[ stops[ u ] ][ stops[ v ] ] );
}
}
}
long long res = INF;
for( int i = 0; i < k; i++ )
res = min( res, dp[ kk - 1 ][ i ] + d[ stops[ i ] ][ n ] );
if( k == 0 )
res = d[ 1 ][ n ];
cout << res << '\n';
return 0;
}