Pagini recente » Cod sursa (job #2178272) | Cod sursa (job #450975) | Cod sursa (job #2787004) | Cod sursa (job #2584797) | Cod sursa (job #2336773)
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz size()
using namespace std ;
const int NR = 50005 ;
const int oo = ( 1 << 30 ) ;
ifstream in ("ubuntzei.in") ;
ofstream out ("ubuntzei.out") ;
vector < pair < int , int > > v [ NR ] ;
vector < int > d ( NR , oo ) ;
bool in_que [ NR ] ;
vector < int > st ;
int n , m , k ;
long long sum ;
struct cmp
{
bool operator () ( int x , int y )
{
return d [ x ] > d [ y ] ;
}
};
priority_queue < int , vector < int > , cmp > q ;
void dijk ( int start )
{
q.push( start ) ;
in_que [ start ] = true ;
d [ start ] = 0 ;
while ( !q.empty() )
{
int nod = q.top() ;
in_que [ nod ] = false ;
q.pop() ;
for ( size_t i = 0 ; i < v [ nod ].sz ; ++ i )
{
int vecin = v [ nod ][ i ].first ;
int cost = v [ nod ][ i ].second ;
if ( d [ nod ] + cost < d [ vecin ] )
{
d [ vecin ] = d [ nod ] + cost ;
if ( !in_que [ vecin ] ) { q.push( vecin ) , in_que [ vecin ] = true ; }
}
}
}
}
int main ()
{
int i ;
in >> n >> m ;
in >> k ;
for ( int i = 1 ; i <= k ; ++ i )
{
int x ; in >> x ;
st.pb ( x ) ;
}
for ( i = 1 ; i <= m ; ++ i )
{
int x , y , c ;
in >> x >> y >> c ;
v [ x ].pb ( mp ( y , c ) ) ;
}
int nod = 1 ;
int cnt = 0 ;
bool viz [ k + 1 ] = {false} ;
while ( k != cnt )
{
dijk( nod ) ;
int best , minim = ( 1 << 30 ) ;
for ( int i = 0 ; i < k ; ++ i )
{
if ( !viz [ i ] && d [ st [ i ] ] < minim ) minim = d [ st [ i ] ] , best = i ;
}
viz [ best ] = true ;
nod = st [ best ] ;
sum += minim ;
cnt ++ ;
for ( int i = 1 ; i <= n ; ++ i ) d [ i ] = oo , in_que [ i ] = false ;
while ( !q.empty() ) q.pop() ;
}
dijk( nod ) ;
out << ( long long) ( sum + d [ n ] ) << "\n" ;
}