Submission #626805

#	Time	Username	Problem	Language	Result	Execution time	Memory
626805		chonka	Cities (BOI16_cities)	C++17	100 / 100	1793 ms	45592 KiB

cities

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

const int MAXN = 2e5 + 7 ;
const ll inf = 1e16 ;


int n , k ;
vector < pair < int , int > > v[ MAXN ] ;
vector < int > spec ;
ll dp[ MAXN ][ 32 ] ;
ll dist[ MAXN ] ;

priority_queue < pair < ll , int > > q ;

void solve ( ) {
    int m ;
    cin >> n >> k >> m ;
    spec.resize ( k ) ;
    for ( int i = 0 ; i < k ; ++ i ) {
        cin >> spec[ i ] ;
    }
    for ( int i = 1 , x , y , z ; i <= m ; ++ i ) {
        cin >> x >> y >> z ;
        v[ x ].push_back ( { y , z } ) ;
        v[ y ].push_back ( { x , z } ) ;
    }
    for ( int mask = 1 ; mask < ( 1 << k ) ; ++ mask ) {
        for ( int i = 1 ; i <= n ; ++ i ) {
            dp[ i ][ mask ] = dist[ i ] = inf ;
        }
        for ( int j = 0 ; j < k ; ++ j ) {
            if ( mask == ( 1 << j ) ) {
                dp[ spec[ j ] ][ mask ] = 0 ;
            }
        }
        for ( int i = 1 ; i <= n ; ++ i ) {
            for ( int sub1 = ( ( mask - 1 ) & mask ) ; sub1 > 0 ; sub1 = ( ( sub1 - 1 ) & mask ) ) {
                dp[ i ][ mask ] = min ( dp[ i ][ mask ] , dp[ i ][ sub1 ] + dp[ i ][ mask - sub1 ] ) ;
            }
        }
        if ( mask == ( 1 << k ) ) { continue ; }
        for ( int i = 1 ; i <= n ; ++ i ) {
            if ( dp[ i ][ mask ] != inf ) {
                dist[ i ] = dp[ i ][ mask ] ;
                q.push ( { -dist[ i ] , i } ) ;
            }
        }
        while ( q.empty ( ) == false ) {
            auto [ cost , x ] = q.top ( ) ; q.pop ( ) ;
            cost = -cost ;
            if ( cost != dist[ x ] ) { continue ; }
            for ( auto [ y , add ] : v[ x ] ) {
                if ( dist[ y ] > cost + add ) {
                    dist[ y ] = cost + add ;
                    q.push ( { -dist[ y ] , y } ) ;
                }
            }
        }
        for ( int i = 1 ; i <= n ; ++ i ) {
            dp[ i ][ mask ] = dist[ i ] ;
        }
    }
    ll ans = inf ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        ans = min ( ans , dp[ i ][ ( 1 << k ) - 1 ] ) ;
    }
    cout << ans << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26