Submission #41586

#	Time	Username	Problem	Language	Result	Execution time	Memory
41586		chonka	Commuter Pass (JOI18_commuter_pass)	C++98	100 / 100	589 ms	20004 KiB

commuter_pass

#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std ;

#define MAXN 200007
long long inf ;

int n , m ;
int p1 , p2 ;
int p3 , p4 ;

vector < pair < int , int > > v[ MAXN ] ;

long long f[ MAXN ][ 5 ] ;
long long dp[ MAXN ][ 3 ] ;

struct tuhla {
    int vertex ;
    long long cost ;
    tuhla ( ) { vertex = cost = 0 ; }
    tuhla ( int _vertex , long long _cost ) {
        vertex = _vertex ;
        cost = _cost ;
    }
};
bool operator < ( tuhla aux1 , tuhla aux2 ) {
    return ( aux1.cost > aux2.cost ) ;
}
priority_queue < tuhla > q ;


void dijkstra ( int vertex , int id ) {
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        f[ i ][ id ] = inf ;
    }
    f[ vertex ][ id ] = 0 ;
    q.push ( tuhla ( vertex , 0 ) ) ;
    while ( q.empty ( ) == false ) {
        tuhla u = q.top ( ) ;
        q.pop ( ) ;
        if ( u.cost != f[ u.vertex ][ id ] ) { continue ; }
        int sz = v[ u.vertex ].size ( ) ;
        for ( i = 0 ; i < sz ; i ++ ) {
            int h = v[ u.vertex ][ i ].first ;
            int c = v[ u.vertex ][ i ].second ;
            if ( f[ h ][ id ] > u.cost + c ) {
                f[ h ][ id ] = u.cost + c ;
                q.push ( tuhla ( h , f[ h ][ id ] ) ) ;
            }
        }
    }
}

void calc_dp ( int vertex , int id , int pos ) {
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        f[ i ][ id ] = inf ;
        dp[ i ][ pos ] = inf ;
    }
    f[ vertex ][ id ] = 0 ;
    dp[ vertex ][ pos ] = f[ vertex ][ 2 ] ;
    q.push ( tuhla ( vertex , 0 ) ) ;
    while ( q.empty ( ) == false ) {
        tuhla u = q.top ( ) ;
        q.pop ( ) ;
        if ( u.cost != f[ u.vertex ][ id ] ) { continue ; }
        int sz = v[ u.vertex ].size ( ) ;
        for ( i = 0 ; i < sz ; i ++ ) {
            int h = v[ u.vertex ][ i ].first ;
            int c = v[ u.vertex ][ i ].second ;
            if ( f[ h ][ id ] > u.cost + c ) {
                f[ h ][ id ] = u.cost + c ;
                q.push ( tuhla ( h , f[ h ][ id ] ) ) ;
                dp[ h ][ pos ] = inf ;
            }
            if ( f[ h ][ id ] == u.cost + c ) {
                dp[ h ][ pos ] = min ( dp[ h ][ pos ] , min ( f[ h ][ 2 ] , dp[ u.vertex ][ pos ] ) ) ;
            }
        }
    }
}

void input ( ) {
    scanf ( "%d%d" , &n , &m ) ;
    scanf ( "%d%d" , &p1 , &p2 ) ;
    scanf ( "%d%d" , &p3 , &p4 ) ;
    int i ;
    for ( i = 1 ; i <= m ; i ++ ) {
        int x , y , z ;
        scanf ( "%d%d%d" , &x , &y , &z ) ;
        v[ x ].push_back ( make_pair ( y , z ) ) ;
        v[ y ].push_back ( make_pair ( x , z ) ) ;
    }
    inf = 1 ;
    for ( i = 1 ; i <= 16 ; i ++ ) {
        inf *= 10 ;
    }
}

void solve ( ) {
    dijkstra ( p3 , 1 ) ;
    dijkstra ( p4 , 2 ) ;
    calc_dp ( p1 , 3 , 1 ) ;
    calc_dp ( p2 , 4 , 2 ) ;
    int i ;
    long long ans = f[ p4 ][ 1 ]  ;
    for ( i = 1 ; i <= n ; i ++ ) {
        if ( f[ i ][ 3 ] + f[ i ][ 4 ] == f[ p2 ][ 3 ] ) {
            long long cur = f[ i ][ 1 ] + min ( dp[ i ][ 1 ] , dp[ i ][ 2 ] ) ;
            if ( ans > cur ) { ans = cur ; }
        }
    }
    printf ( "%lld\n" , ans ) ;
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void input()':
commuter_pass.cpp:87:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d" , &n , &m ) ;
                                ^
commuter_pass.cpp:88:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d" , &p1 , &p2 ) ;
                                  ^
commuter_pass.cpp:89:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d" , &p3 , &p4 ) ;
                                  ^
commuter_pass.cpp:93:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d%d%d" , &x , &y , &z ) ;
                                           ^

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45