Submission #1250987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250987		duyen	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	195 ms	22500 KiB

commuter_pass

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

struct Edge {
    int to;
    ll w;
};

vector<ll> dijkstra(int src, const vector<vector<Edge>>& g) {
    int n = g.size();
    vector<ll> dist(n, INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    dist[src] = 0;
    pq.emplace(0, src);
    while (!pq.empty()) {
        auto [d,u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto& e : g[u]) {
            int v = e.to; ll w = e.w;
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    return dist;
}

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

    int N, M;
    cin >> N >> M;
    int S, T, U, V;
    cin >> S >> T >> U >> V;
    --S; --T; --U; --V;

    vector<vector<Edge>> G(N);
    struct E2 { int u, v; ll c; };
    vector<E2> edges;
    edges.reserve(M);

    for(int i = 0; i < M; i++){
        int a, b;
        ll c;
        cin >> a >> b >> c;
        --a; --b;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
        edges.push_back({a,b,c});
    }

    // 1) Run Dijkstra from S, T, U, V
    auto dS = dijkstra(S, G);
    auto dT = dijkstra(T, G);
    auto dU = dijkstra(U, G);
    auto dV = dijkstra(V, G);

    ll distST = dS[T];

    // 2) Collect all nodes lying on *some* shortest S->T path:
    //    those v with dS[v] + dT[v] == distST
    vector<int> onST;
    onST.reserve(N);
    for(int v = 0; v < N; v++){
        if (dS[v] < INF && dT[v] < INF && dS[v] + dT[v] == distST) {
            onST.push_back(v);
        }
    }
    // 3) Sort them in increasing order of dS[]
    sort(onST.begin(), onST.end(),
         [&](int a, int b){
             return dS[a] < dS[b];
         });

    // 4) DP sweep: best_dU = min dU[a] over all 'a' seen so far;
    //    then for current node b, minCost = min(minCost, best_dU + dV[b]).
    //    This captures taking the free-pass segment from 'a'->...->b on some
    //    S-T shortest path (all such segments are in the DAG of onST).
    ll ans = dU[V];          // case: take no free segment at all
    ll best_dU = INF;
    for(int v : onST) {
        best_dU = min(best_dU, dU[v]);
        if (best_dU < INF && dV[v] < INF) {
            ans = min(ans, best_dU + dV[v]);
        }
    }

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

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