Submission #1241955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241955		trantien3771	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	155 ms	19768 KiB

commuter_pass

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

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

    int N, M;
    cin >> N >> M;
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    vector<vector<pair<int,ll>>> adj(N+1);
    for (int i = 0; i < M; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    auto dijkstra = [&](int src) {
        vector<ll> dist(N+1, INF);
        vector<int> parent(N+1, -1);
        dist[src] = 0;
        priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
        pq.push({0, src});
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dist[u]) continue;
            for (auto &e : adj[u]) {
                int v = e.first;
                ll w = e.second;
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    parent[v] = u;
                    pq.push({dist[v], v});
                }
            }
        }
        return make_pair(dist, parent);
    };

    // 1) Dijkstra từ A để lấy đường đi tới B
    auto [dA, parA] = dijkstra(A);
    // Thu hồi path A -> B
    vector<int> path;
    int cur = B;
    while (cur != -1) {
        path.push_back(cur);
        if (cur == A) break;
        cur = parA[cur];
    }
    reverse(path.begin(), path.end());
    int K = path.size();

    // 2) Dijkstra từ C và D
    auto [dC, _] = dijkstra(C);
    auto [dD, __] = dijkstra(D);

    // 3) Lấy fC và fD trên path
    vector<ll> fC(K), fD(K);
    for (int i = 0; i < K; i++) {
        int u = path[i];
        fC[i] = dC[u];
        fD[i] = dD[u];
    }

    // 4) Suffix-min trên fD
    vector<ll> suf(K);
    suf[K-1] = fD[K-1];
    for (int i = K-2; i >= 0; i--) {
        suf[i] = min(fD[i], suf[i+1]);
    }

    // 5) Tính phương án mua VIP
    ll ansVip = INF;
    for (int i = 0; i < K; i++) {
        // C -> path[i] trả phí + đi miễn phí đến bất kỳ path[j] j>=i + path[j] -> D trả phí
        ansVip = min(ansVip, fC[i] + suf[i]);
    }

    // 6) Phương án không mua VIP
    ll ansNoVip = dC[D];

    ll result = min(ansVip, ansNoVip);
    if (result >= INF/2) result = -1;
    cout << result;

    return 0;
}

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