Submission #1144314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144314		quangnamoiracvl_ralaidecu	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	238 ms	19936 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; 
};
struct cmp{
    bool operator()( const mimi a, const mimi b ){
        return a.w < b.w; 
    }
};
vector< pair > g[N];  
tn n, m, w, a, b, s, t, u, v, result = 1e18, dist[N][2]; 
mimi dick[N];
priority_queue< mimi, vector< mimi >, cmp > Q;
priority_queue< pair, vector< pair >, greater< pair > > 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;
                q.push( { dist[v.fi][type], v.fi } );
            }
        }
    }
}
void bfs(){
    dick[s].w = 0; dick[s].a = dist[s][0]; dick[s].b = dist[s][1]; 
    result = min( result, dick[s].a + dick[s].b ); 
    q.push( { 0, s } ); 
    while ( !q.empty() ){
        tn u = q.top().se; 
        tn cost = q.top().fi;
        q.pop(); 
        if ( cost > dick[u].w )
            continue; 
        for ( auto v : g[u] ){
            if ( dick[v.fi].w > dick[u].w + v.se ){
                dick[v.fi].w = dick[u].w + v.se; 
                dick[v.fi].a = min( dick[u].a, dist[v.fi][0] ); 
                dick[v.fi].b = min( dick[u].b, dist[v.fi][1] );
                q.push( { dick[v.fi].w, v.fi } );  
            }
            else if ( dick[v.fi].w == dick[u].w + v.se ){
                if ( dick[v.fi].a + dick[v.fi].b > dick[u].a + dick[u].b ) 
                    dick[v.fi].a = dick[u].a, 
                    dick[v.fi].b = dick[u].b;
            }
        }
    }   
}
signed main(){
    thaonguyenxinh 
    // hi skibidi 
    cin >> n >> m >> s >> t >> a >> b;
    thaonguyen( i, 1, n ) 
        dist[i][0] = dist[i][1] = dist[i][2] = 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 ); bfs(); 
    cout << min( dist[a][1], dick[t].a + dick[t].b ); 
}

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