Submission #1224777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224777		nanaseyuzuki	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	220 ms	38420 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;
};

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<Edge>> adj(n+1);
    struct Raw{int u,v; ll w;};
    vector<Raw> raw;
    raw.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});
        raw.push_back({u,v,w});
    }

    // 1) Dijkstra từ A và B để tính d1[], d2[]
    auto dijkstra = [&](int src){
        vector<ll> d(n+1, INF);
        d[src]=0;
        priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
        pq.push({0, src});
        while(!pq.empty()){
            auto [du,u] = pq.top(); pq.pop();
            if(du>d[u]) continue;
            for(auto &e: adj[u]){
                int v=e.to; ll w=e.w;
                if(d[v] > du + w){
                    d[v] = du + w;
                    pq.push({d[v], v});
                }
            }
        }
        return d;
    };

    auto d1 = dijkstra(A);
    auto d2 = dijkstra(B);
    ll L = d1[B];

    // 2) Đánh dấu special-edge
    vector<unordered_set<int>> special(n+1);
    for(int u=1;u<=n;u++){
        for(auto &e: adj[u]){
            int v=e.to; ll w=e.w;
            if(d1[u] + w + d2[v] == L){
                special[u].insert(v);
            }
        }
    }

    // 3) Dijkstra trên đồ thị 3-state cho chiều C->D
    // dist[u][s]: min cost tới (u, state s)
    vector<array<ll,3>> dist(n+1);
    for(int i=1;i<=n;i++) dist[i] = {INF,INF,INF};
    dist[C][0] = 0;
    // pq: (cost, u, state)
    struct Node{ ll d; int u,s; };
    struct Cmp{ bool operator()(Node const &a, Node const &b) const {
        return a.d > b.d;
    }};
    priority_queue<Node, vector<Node>, Cmp> pq;
    pq.push({0, C, 0});

    while(!pq.empty()){
        auto [du,u,s] = pq.top(); pq.pop();
        if(du > dist[u][s]) continue;
        for(auto &e: adj[u]){
            int v=e.to; ll w=e.w;
            if(s==0){
                // chưa vào special
                if(special[u].count(v)){
                    // bước vào đường A->B
                    if(dist[v][1] > du){
                        dist[v][1] = du;
                        pq.push({du, v, 1});
                    }
                }
                // đi thường
                if(dist[v][0] > du + w){
                    dist[v][0] = du + w;
                    pq.push({du + w, v, 0});
                }
            }
            else if(s==1){
                // đang trên special-path
                if(special[u].count(v)){
                    // tiếp tục special
                    if(dist[v][1] > du){
                        dist[v][1] = du;
                        pq.push({du, v, 1});
                    }
                } else {
                    // rời special, sang state 2
                    if(dist[v][2] > du + w){
                        dist[v][2] = du + w;
                        pq.push({du + w, v, 2});
                    }
                }
            }
            else {
                // s==2: đã rời, chỉ đi thường
                if(dist[v][2] > du + w){
                    dist[v][2] = du + w;
                    pq.push({du + w, v, 2});
                }
            }
        }
    }

    ll ans = min({dist[D][0], dist[D][1], dist[D][2]});
    if(ans >= INF/2) ans = -1; // hoặc tuỳ đề, INF nghĩa không tới được
    cout << ans << "\n";
    return 0;
}

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