Submission #1218035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218035		teslerpham	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	211 ms	18416 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define el '\n'

using ll  = long long;
using pii = pair<int,int>;
using vi  = vector<int>;
using vll = vector<ll>;

const ll LINF = (ll)4e18;

void fastIO(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

vector<vector<pii>> adj;
int n, m;
vll dU, dV, distS, distT, dpF, dpB, distF, distB;

vll dijkstra(int src){
    vll d(n, LINF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    d[src] = 0; pq.emplace(0, src);
    while(!pq.empty()){
        auto [du,u] = pq.top(); pq.pop();
        if(du > d[u]) continue;
        for(auto [v,w]: adj[u]){
            ll nd = du + w;
            if(nd < d[v]){
                d[v] = nd;
                pq.emplace(nd, v);
            }
        }
    }
    return d;
}

void dp_run(int start, vll &dist, vll &dp){
    // dist[...] and dp[...] initialized to LINF
    dist[start] = 0;
    dp[start]   = dV[start];
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    pq.emplace(0, start);
    while(!pq.empty()){
        auto [du,u] = pq.top(); pq.pop();
        if(du > dist[u]) continue;
        ll pre = dp[u];
        for(auto [v,w]: adj[u]){
            ll nd = du + w;
            if(nd < dist[v]){
                dist[v] = nd;
                dp[v]   = min(pre, dV[v]);
                pq.emplace(nd, v);
            } else if(nd == dist[v]){
                dp[v] = min(dp[v], min(pre, dV[v]));
            }
        }
    }
}

int main(){
    fastIO();

    cin >> n >> m;
    int S, T, U, V; 
    cin >> S >> T >> U >> V;
    --S; --T; --U; --V;

    adj.assign(n, {});
    for(int i = 0; i < m; i++){
        int a,b; ll c;
        cin >> a >> b >> c;
        --a; --b;
        adj[a].eb(b,c);
        adj[b].eb(a,c);
    }

    dU = dijkstra(U);
    dV = dijkstra(V);

    distS = dijkstra(S);
    distT = dijkstra(T);
    ll bestST = distS[T];

    // 3) Forward DP from S
    distF.assign(n, LINF);
    dpF  .assign(n, LINF);
    dp_run(S, distF, dpF);

    // 4) Backward DP from T
    // reuse adj but run from T
    distB.assign(n, LINF);
    dpB  .assign(n, LINF);
    dp_run(T, distB, dpB);

    ll ans = dU[V];  // no pass
    for(int i = 0; i < n; i++){
        if(distF[i] + distB[i] == bestST){
            ll via = min(dpF[i], dpB[i]) + dU[i];
            ans = min(ans, via);
        }
    }

    cout << ans << el;
    return 0;
}

/*
⢀⡴⠑⡄⠀⠀⠀⠀⠀⠀⠀⣀⣀⣤⣤⣤⣀⡀      Monkey D. LUFFY
⠸⡇⠀⠿⡀⠀⣀⡴⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⡀   "I’m gonna be..."
⠀⠀⠀⠀⠑⢄⣾⣷⣶⣶⣶⣶⣶⣶⣶⣶⣶⣶⣶⣯⣍⠻⣷⡄   ...King of the Pirates!
⠀⠀⠀⠀⢀⡀⠁⠈⠙⠻⠿⠿⠿⠿⠿⠿⠿⠿⠿⠿⠿⠟⠋   ⠀
⠀⠀⠀⢀⡾⣁⣀⠀⠴⠂⠙⣗⡀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⣴⣷⠘⠿⠛⠃⠀⠀⠀⠉⠳⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⣴⣿⠙⣆⠀⠀⠀⠀⠀⠀⠀⠈⠙⠒⠊⠁⠀⠀⠀⠀⠀
⢀⣼⣿⠀⣇⣀⠀⠀⣠⣤⣶⣾⣿⣶⣶⣶⣶⠆⠀⠀⠀⠀

*/

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