Cod sursa(job #2336772)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 5 februarie 2019 15:51:16
Problema Ubuntzei Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#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 ("dijkstra.in") ;
ofstream out ("dijkstra.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" ;
}