Submission #1130429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130429		akzytr	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	1010 ms	30480 KiB

commuter_pass

#include <bits/stdc++.h>
#define ve vector
#define ar array 
#define pb push_back
#define ins insert

#define endl '\n'
#define ll long long
using namespace std;


const int MXN = 2e5+1;
int N, M, S, T, U, V;
ve<pair<int, int>> adj[MXN];

ve<ll> ds(MXN, 1e18);
ve<ll> du(MXN, 1e18);
ve<ll> dv(MXN, 1e18);
ve<ll> dpu(MXN, 1e18);
ve<ll> dpv(MXN, 1e18);

ll ans = 8e18;
void djikstra(ve<ll> &dst, int strt){
    set<pair<ll, int>> pq;
    pq.insert({0, strt});
    while(!pq.empty()){
        auto top = *pq.begin();
        pq.erase(pq.begin());
        if(top.first < dst[top.second]){
            dst[top.second] = top.first;
            for(auto [x, c] : adj[top.second]){
                pq.insert({c + top.first, x});
            }
        }
    }
}

void djikstra2(int strt, int end, ve<ll> &d_strt){
    set<ar<ll, 3>> pq;
    pq.insert({0, strt, strt});
    ve<bool> vis(MXN, 0);
    while(!pq.empty()){
        auto [c, x, par] = *pq.begin();
        pq.erase(pq.begin());

        if(c != d_strt[x]){
            vis[x] = 1;
            continue;
        }

        if(c == d_strt[x]){
            if(min(dpu[par], du[x]) + min(dpv[par], dv[x]) < dpu[x] + dpv[x]){
                dpu[x] = min(dpu[par], du[x]);
                dpv[x] = min(dpv[par], dv[x]);
            }
            if(!vis[x]){
                for(auto [l, cs] : adj[x]){
                    pq.insert({cs + c, l, x});
                }
            }
            vis[x] = 1;
        }
    }
    ans = min(ans, dpu[end] + dpv[end]);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    cin >> S >> T;
    cin >> U >> V;
    for(int i = 0; i < M; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].pb({b, c});
        adj[b].pb({a, c});
    }
    djikstra(ds, S);
    djikstra(du, U);
    djikstra(dv, V);
    ans = du[V];
    djikstra2(S, T, ds);
    // djikstra2(T, S, ds);
    cout << ans << endl;
}

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