Submission #1241957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241957		trantien3771	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	228 ms	22700 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);
    struct Edge{ int u,v; ll w; };
    vector<Edge> edges;
    edges.reserve(M);
    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});
        edges.push_back({u,v,w});
    }

    auto dijkstra = [&](int src){
        vector<ll> dist(N+1, INF);
        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;
                    pq.push({dist[v], v});
                }
            }
        }
        return dist;
    };

    // 1) Khoảng cách từ A, C, D
    auto dA = dijkstra(A);
    auto dC = dijkstra(C);
    auto dD = dijkstra(D);

    // 2) Xây DAG của mọi cạnh thuộc shortest-paths A->B
    //    nếu dA[u] + w == dA[v] thì có cung u->v
    vector<vector<int>> dag(N+1);
    for(auto &E: edges){
        int u = E.u, v = E.v; ll w = E.w;
        if(dA[u] + w == dA[v]){
            dag[u].push_back(v);
        }
        if(dA[v] + w == dA[u]){
            dag[v].push_back(u);
        }
    }

    // 3) Trên DAG định thứ tự topo rất đơn giản: tăng dA[]
    vector<int> ord(N);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [&](int x, int y){
        return dA[x] < dA[y];
    });

    // 4) DP: duyệt qua từng cung u->v, coi mua VIP trên cung đó,
    //    chi phí = dC[u] + dD[v]
    ll ansVip = INF;
    for(int u: ord){
        for(int v: dag[u]){
            // nếu cung này nằm trên 1 đường ngắn nhất A->B
            ansVip = min(ansVip, dC[u] + dD[v]);
        }
    }

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

    ll res = min(ansVip, ansNoVip);
    if(res >= INF/2) res = -1;
    cout << res << "\n";
    return 0;
}

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