Submission #1160094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160094		algo-cooker	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	321 ms	24280 KiB

commuter_pass

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll inf=1e18;

ll n,m,s,t,u,v;
vector<vector<pair<ll,ll>>> g;
vector<ll> d[2];

vector<ll> d2[2];
vector<ll> dp[2];

void dij(ll x, ll y){
    for(ll i=0; i<=n+1; i++) d[y].push_back(inf);
    d[y][x]=0;
    set<pair<ll,ll>> ds;
    ds.insert({0, x});

    while(!ds.empty()){
        auto v = *ds.begin();
        ds.erase(ds.begin());

        for(auto u: g[v.second]){
            if(d[y][u.first] > d[y][v.second]+u.second){
                ds.erase({d[y][u.first],u.first});
                d[y][u.first] = d[y][v.second]+u.second;
                ds.insert({d[y][u.first],u.first});
            }
        }
    }
}

void dij2(ll x, ll y){
    for(ll i=0; i<=n+1; i++) d2[y].push_back(inf);
    for(ll i=0; i<=n+1; i++) dp[y].push_back(inf);

    d2[y][x]=0; dp[y][x]=d[0][x];

    set<pair<ll,ll>> ds;
    ds.insert({0, x});

    while(!ds.empty()){
        auto v = *ds.begin();
        ds.erase(ds.begin());

        for(auto u: g[v.second]){
            if(d2[y][u.first] > d2[y][v.second]+u.second){
                ds.erase({d2[y][u.first],u.first});
                d2[y][u.first] = d2[y][v.second]+u.second;
                dp[y][u.first] = min(dp[y][v.second], d[0][u.first]);
                ds.insert({d2[y][u.first],u.first});
            }
            else if(d2[y][u.first] == d2[y][v.second]+u.second){
                dp[y][u.first] = min({dp[y][u.first], dp[y][v.second], d[0][u.first]});
            }
        }
    }
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> s >> t >> u >> v;
    g = vector<vector<pair<ll,ll>>>(n+1);

    for(ll i=0; i<m; i++){
        ll a,b,c; cin >> a >> b >> c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }

    dij(u,0);
    dij(v,1);

    dij2(s,0);
    dij2(t,1);

    ll ans = d[1][u];
    for(ll i=1; i<=n; i++){
        if(d2[0][i]+d2[1][i] != d2[0][t]) continue;
        ans = min(ans, dp[0][i]+d[1][i]);
    }

    for(ll i=1; i<=n; i++){
        if(d2[1][i]+d2[0][i] != d2[1][s]) continue;
        ans = min(ans, dp[1][i]+d[1][i]);
    }

    cout << ans << '\n';
    return 0;
}

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