Submission #1193227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193227		vux2code	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	202 ms	30520 KiB

commuter_pass

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

vector<ll> dijkstra(int src, const vector<vector<pair<int,ll>>> &adj) {
    int n = adj.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 &pr : adj[u]) {
            int v = pr.first;
            ll w = pr.second;
            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(NULL);

    int N, M;
    cin >> N >> M;
    int S, T;
    cin >> S >> T;
    int U, V;
    cin >> U >> V;
    // 1-indexed; resize to N+1
    vector<vector<pair<int,ll>>> adj(N+1);
    struct Edge { int a, b; ll c; };
    vector<Edge> edges;
    edges.reserve(M);
    for (int i = 0; i < M; i++) {
        int a, b; ll c;
        cin >> a >> b >> c;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
        edges.push_back({a, b, c});
    }
    
    // shortest distances
    auto dS = dijkstra(S, adj);
    auto dT = dijkstra(T, adj);
    auto dU = dijkstra(U, adj);
    auto dV = dijkstra(V, adj);
    ll D = dS[T];
    
    // build SP DAG
    vector<vector<int>> dag(N+1), dag_rev(N+1);
    for (auto &e : edges) {
        int a = e.a, b = e.b;
        ll c = e.c;
        if (dS[a] + c + dT[b] == D) {
            dag[a].push_back(b);
            dag_rev[b].push_back(a);
        }
        if (dS[b] + c + dT[a] == D) {
            dag[b].push_back(a);
            dag_rev[a].push_back(b);
        }
    }
    
    // find DAG nodes reachable from S and reaching T
    vector<char> fromS(N+1, 0), toT(N+1, 0);
    // BFS from S in dag
    deque<int> q;
    q.push_back(S);
    fromS[S] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop_front();
        for (int v : dag[u]) {
            if (!fromS[v]) {
                fromS[v] = 1;
                q.push_back(v);
            }
        }
    }
    // BFS from T in reverse dag
    q.clear();
    q.push_back(T);
    toT[T] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop_front();
        for (int v : dag_rev[u]) {
            if (!toT[v]) {
                toT[v] = 1;
                q.push_back(v);
            }
        }
    }
    
    // collect relevant DAG nodes
    vector<int> sp_nodes;
    sp_nodes.reserve(N);
    for (int i = 1; i <= N; i++) {
        if (fromS[i] && toT[i]) sp_nodes.push_back(i);
    }
    // sort by dS increasing (topological order)
    sort(sp_nodes.begin(), sp_nodes.end(), [&](int a, int b) {
        return dS[a] < dS[b];
    });
    
    // DP for Bmin: minimal dV reachable from u in DAG
    unordered_map<int,ll> Bmin;
    Bmin.reserve(sp_nodes.size());
    for (int u : sp_nodes) {
        Bmin[u] = dV[u];
    }
    // process in reverse order
    for (int idx = (int)sp_nodes.size() - 1; idx >= 0; idx--) {
        int u = sp_nodes[idx];
        for (int v : dag[u]) {
            if (toT[v]) {
                Bmin[u] = min(Bmin[u], Bmin[v]);
            }
        }
    }
    
    // compute answer
    ll ans = dU[V];  // without using pass
    for (int u : sp_nodes) {
        if (dU[u] < INF && Bmin[u] < INF) {
            ans = min(ans, dU[u] + Bmin[u]);
        }
    }
    cout << ans;
    return 0;
}

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