Submission #1241953

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241953		khanhtt	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	222 ms	14472 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)1e18;

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

    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    vector<vector<pair<int,int>>> adj(n+1);
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].emplace_back(b,c);
        adj[b].emplace_back(a,c);
    }

    // Standard Dijkstra from a single source.
    auto dijkstra = [&](int src){
        vector<ll> dist(n+1, INF);
        priority_queue<pair<ll,int>,
                       vector<pair<ll,int>>,
                       greater<>> pq;
        dist[src] = 0;
        pq.push({0, src});
        while(!pq.empty()){
            auto [d, x] = pq.top(); pq.pop();
            if(d > dist[x]) continue;
            for(auto [y, w] : adj[x]){
                if(d + w < dist[y]){
                    dist[y] = d + w;
                    pq.push({dist[y], y});
                }
            }
        }
        return dist;
    };

    auto du = dijkstra(u);
    auto dv = dijkstra(v);
    auto ds = dijkstra(s);

    // If t is unreachable from s, no valid path:
    if(ds[t] == INF){
        cout << "-1\n";
        return 0;
    }

    // DP arrays: bestU[i], bestV[i] = 
    //   the minimal possible (min du on s→i + min dv on s→i) 
    //   if you choose the "worst" path deliberately.
    vector<ll> bestU(n+1, INF), bestV(n+1, INF);

    // Base at s:
    bestU[s] = du[s];
    bestV[s] = dv[s];

    // Sort nodes by increasing ds[]
    vector<int> order(n);
    iota(order.begin(), order.end(), 1);
    sort(order.begin(), order.end(),
         [&](int a, int b){ return ds[a] < ds[b]; });

    // Relax along the DAG of shortest‐path edges,
    // but *minimize* bestU+bestV instead of maximize.
    for(int x : order){
        if(bestU[x] == INF) continue;  // no s→x path in our DP
        for(auto [y, w] : adj[x]){
            if(ds[x] + w == ds[y]) {
                ll candU = min(bestU[x], du[y]);
                ll candV = min(bestV[x], dv[y]);
                if(candU + candV < bestU[y] + bestV[y]){
                    bestU[y] = candU;
                    bestV[y] = candV;
                }
            }
        }
    }

    // Output the *minimum* sum of the two minima on any shortest s→t:
    cout << (bestU[t] + bestV[t]) << "\n";
    return 0;
}

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