oj.uz

Submission #626805

# Submission time Handle Problem Language Result Execution time Memory
626805 2022-08-11T20:00:34 Z chonka Cities (BOI16_cities) C++17
100 / 100
 1793 ms 45592 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4968 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5048 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 45532 KB Output is correct
2 Correct 414 ms 45112 KB Output is correct
3 Correct 249 ms 38300 KB Output is correct
4 Correct 72 ms 13344 KB Output is correct
5 Correct 261 ms 45512 KB Output is correct
6 Correct 54 ms 13388 KB Output is correct
7 Correct 5 ms 5332 KB Output is correct
8 Correct 4 ms 5420 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5448 KB Output is correct
2 Correct 7 ms 5332 KB Output is correct
3 Correct 5 ms 5332 KB Output is correct
4 Correct 7 ms 5204 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 904 ms 45516 KB Output is correct
2 Correct 858 ms 45352 KB Output is correct
3 Correct 624 ms 38272 KB Output is correct
4 Correct 477 ms 30008 KB Output is correct
5 Correct 133 ms 16720 KB Output is correct
6 Correct 62 ms 14948 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1765 ms 45592 KB Output is correct
2 Correct 1793 ms 45500 KB Output is correct
3 Correct 1709 ms 45248 KB Output is correct
4 Correct 1197 ms 38372 KB Output is correct
5 Correct 913 ms 29968 KB Output is correct
6 Correct 205 ms 16756 KB Output is correct
7 Correct 67 ms 14936 KB Output is correct