Submission #1144553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144553		quangnamoiracvl_ralaidecu	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	2098 ms	327680 KiB

commuter_pass

// Author : Thao Nguyen Xinh 
// Codeforces Handle : thaonguyendethuongvai
#include<bits/stdc++.h> 
using namespace std; 
#define endl "\n" 
#define tn long long 
#define fi first 
#define se second 
#define pair pair< tn, tn > 
#define thaonguyen( i, a, b ) for( tn i = a; i <= b; i++ ) 
#define nguyenthao( i, a, b ) for( tn i = a; i >= b; i-- ) 
#define thaonguyenxinh ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
const tn N = 1e5 + 5;
struct mimi{
    tn u, w, a, b, p; 
};
struct skibidi{
    tn u, a, b; 
};
vector< tn > previous[N];
vector< pair > g[N];  
tn n, m, w, a, b, s, t, u, v, result = 1e18, dist[N][3]; 
mimi dick[N];
//priority_queue< skibidi, vector< skibidi >, cmp > Q;
priority_queue< pair, vector< pair >, greater< pair > > q;  
queue< skibidi > Q;
void dijkstra( tn start, tn type ){
    dist[start][type] = 0; 
    q.push( { 0, start } ); 
    while(!q.empty() ){
        u = q.top().se;  
        tn cost = q.top().fi; 
        q.pop(); 
        if ( cost > dist[u][type] ) 
            continue;
        for ( auto v : g[u] ){
            if ( dist[v.fi][type] > cost + v.se ){
                dist[v.fi][type] = cost + v.se;
                if ( type == 2 ){
                    previous[v.fi].clear(); 
                    previous[v.fi].push_back( u );
                }
                q.push( { dist[v.fi][type], v.fi } );
            }
            else if ( dist[v.fi][type] == cost + v.se and type == 2 )
                previous[v.fi].push_back(u); 
        }
    }
}
void trace(){
    Q.push( { t, dist[t][0], dist[t][1] } ); 
    while ( !Q.empty() ){
        tn u = Q.front().u; 
        tn a = Q.front().a; 
        tn b = Q.front().b; 
        result = min( result, a + b ); 
        Q.pop();
        for ( auto v : previous[u] ){
            Q.push( { v, min( a, dist[v][0] ), min( b, dist[v][1] ) } ); 
        }
    }
}
signed main(){
    thaonguyenxinh 
    // hi skibidi 
    cin >> n >> m >> s >> t >> a >> b;
    thaonguyen( i, 1, n ) 
        dist[i][0] = 1e18,
        dist[i][1] = 1e18, 
        dist[i][2] = 1e18,
        dick[i].w = 1e18;
    thaonguyen( i, 1, m ){
        cin >> u >> v >> w;
        g[u].push_back( { v, w } );
        g[v].push_back( { u, w } );
    }
    dijkstra( a, 0 ); dijkstra( b, 1 ); dijkstra( s, 2 ); trace(); 
    cout << min( dist[a][1], result );
}

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