Submission #1286746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286746		harryleee	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	386 ms	22296 KiB

commuter_pass

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

struct Edge {
    int u, v;
    int w;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    int S, T, U, V;
    if (!(cin >> n >> m >> S >> T >> U >> V)) return 0;
    vector<Edge> edges(m+1);
    vector<vector<pair<int,int>>> adj(n+1);
    for (int i = 1; i <= m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        edges[i] = {a,b,c};
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }

    auto dijkstra_from = [&](int src) {
        vector<ll> dist(n+1, INF);
        priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
        dist[src] = 0;
        pq.push({0, src});
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d != dist[u]) continue;
            for (auto [v, eid] : adj[u]) {
                int w = edges[eid].w;
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    pq.push({dist[v], v});
                }
            }
        }
        return dist;
    };

    vector<ll> distS = dijkstra_from(S);
    vector<ll> distT = dijkstra_from(T);
    vector<ll> distU = dijkstra_from(U);
    vector<ll> distV = dijkstra_from(V);

    // Mark edges that lie on some shortest path from S to T and build directed DAG (forward along distS)
    vector<vector<int>> dag(n+1);
    for (int i = 1; i <= m; ++i) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        // if u->v is forward on some shortest S->T path
        if (distS[u] + w + distT[v] == distS[T] && distS[u] + w == distS[v]) {
            dag[u].push_back(v);
        }
        if (distS[v] + w + distT[u] == distS[T] && distS[v] + w == distS[u]) {
            dag[v].push_back(u);
        }
    }

    // sort vertices by distS (increasing). Edges in dag go from smaller distS to larger distS
    vector<int> ord(n);
    for (int i = 0; i < n; ++i) ord[i] = i+1;
    sort(ord.begin(), ord.end(), [&](int a, int b){ return distS[a] < distS[b]; });

    auto solve_with_shop = [&](const vector<ll>& distShop) {
        // DP: best[u] = minimal value of min(distShop[x]) along any path from S to u in DAG
        vector<ll> best(n+1, INF);
        best[S] = distShop[S];
        ll res = INF;
        for (int u : ord) {
            if (best[u] == INF) continue; // unreachable in DAG from S
            // candidate answer: choose route such that up to u we use zero cost, then pay distV[u]
            res = min(res, best[u] + distV[u]);
            for (int v : dag[u]) {
                ll cand = min(best[u], distShop[v]);
                if (cand < best[v]) best[v] = cand;
            }
        }
        return res;
    };

    // Two possibilities: choose route and pay remaining either using shop U->V or swap shops?
    // The original logic runs solve starting from shop1 and then swap shop1/shop2; we mimic that:
    vector<ll> distShop1 = distU;
    vector<ll> distShop2 = distV;
    // first candidate: no zero-route used (just pay direct U->V)
    ll answer = min(distShop1[V], distShop2[U]); // direct without any road chosen (both directions considered)
    // try using DAG + shop1 as "free" source along route
    ll cand1 = solve_with_shop(distShop1);
    // now swap roles: we want shop2 as free-source and distU used as distV vector in lambda, so we need to rebuild lambda using other distV
    // simplest: swap global distV (used in lambda). We'll implement solve_with_shop2 to use distU as second distance:
    // For clarity, duplicate function to use appropriate distal second term.
    auto solve_with_shop_and_other = [&](const vector<ll>& distShop, const vector<ll>& otherDist) {
        vector<ll> best(n+1, INF);
        best[S] = distShop[S];
        ll res2 = INF;
        for (int u : ord) {
            if (best[u] == INF) continue;
            res2 = min(res2, best[u] + otherDist[u]);
            for (int v : dag[u]) {
                ll cand = min(best[u], distShop[v]);
                if (cand < best[v]) best[v] = cand;
            }
        }
        return res2;
    };

    ll candA = solve_with_shop_and_other(distShop1, distV); // original: best + dis_shop2[u]  where shop2==V
    ll candB = solve_with_shop_and_other(distShop2, distU); // swapped roles
    answer = min(answer, min({candA, candB}));

    if (answer >= INF/4) answer = -1; // if unreachable, depends on problem statement (but keep existing)
    cout << answer << "\n";
    return 0;
}

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