Submission #1221706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221706		madamadam3	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	380 ms	42672 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

#define int long long int

using pi = pair<int, int>;
using vb = vector<bool>;
using vi = vector<int>;
using vvi = vector<vi>;
using vpi = vector<pi>;
using vvpi = vector<vpi>;

const int MAXN = 100'001, MAXM = 200'001;
const int INF = 1e18;
int n, m, X[MAXM], Y[MAXM], C[MAXM];
int S, T, U, V;
vi adj[MAXN], mst_adj[MAXN];

void dijkstra(int u, vi &dist, vi &par) {
    dist.assign(n+1, INF);
    par.assign(n+1, -1);

    dist[u] = 0; par[u] = -1;
    priority_queue<pi, vector<pi>, greater<pi>> q;
    q.push({0, u});

    while (!q.empty()) {
        auto cur = q.top();
        q.pop();

        int cu = cur.second, cdist = cur.first;

        for (auto &el : adj[cu]) {
            int cv = X[el] == cu ? Y[el] : X[el];
            int vdist = C[el];

            if(dist[cu] + vdist < dist[cv]) {
                par[cv] = cu;
                dist[cv] = dist[cu] + vdist;
                q.push({dist[cu] + vdist, cv});
            }
        }
    }
}

vi get_topsort(vi &dist, vvi &children) {
    children.assign(n+1, vi());
    vi deg(n+1, 0); 
    for (int i = 1; i <= n; i++) {
        for (auto &eid : adj[i]) {
            int cv = X[eid] == i ? Y[eid] : X[eid], cd = C[eid];
            if (dist[cv] + cd != dist[i]) continue;
            children[cv].push_back(i);
            deg[i]++;
        }
    }

    vi st; for (int i = 1; i <= n; i++) if (deg[i] == 0) st.push_back(i);
    vi order;
    while (!st.empty()) {
        int cur = st.back();
        st.pop_back();

        for (auto &el : children[cur]) {
            deg[el]--;
            if (deg[el] == 0) st.push_back(el);
        }

        order.push_back(cur);
    }

    return order;
}

signed main() {
    cin >> n >> m;
    cin >> S >> T >> U >> V;

    for (int i = 1; i <= m; i++) {
        cin >> X[i] >> Y[i] >> C[i];
        adj[X[i]].push_back(i);
        adj[Y[i]].push_back(i);
    }

    vvi dist(n+1, vi());
    vvi parents(n+1, vi());

    // for (int i = 1; i <= n; i++) {
    for (int i : {S, T, U, V}) {
        dijkstra(i, dist[i], parents[i]);
    }

    int stdist = dist[S][T];
    vb is_on_sp(n+1, false);
    vi on_sp; for (int i = 1; i <= n; i++) {
        if (dist[S][i] + dist[T][i] != stdist) continue;
        on_sp.push_back(i);
        is_on_sp[i] = true;
    }

    vvi ts1_adj, ts2_adj;
    vi stop = get_topsort(dist[S], ts1_adj), ttop = get_topsort(dist[T], ts2_adj);
    vi bestU(n+1, INF), bestV(n+1, INF);

    int best = dist[U][V];
    for (int i : stop) {
        if (!is_on_sp[i]) continue;
        bestU[i] = min(bestU[i], dist[U][i]);
        for (auto &v : ts1_adj[i]) {
            bestU[v] = min(bestU[v], bestU[i]);
        }

        best = min(best, bestU[i] + dist[V][i]); 
    }

    for (auto it = stop.rbegin(); it != stop.rend(); ++it) {
    int v = *it;
    if (dist[S][v] + dist[T][v] == dist[S][T]) {
        bestV[v] = min(bestV[v], dist[U][v]);          
        for (int w : ts2_adj[v])                       
            bestV[w] = min(bestV[w], bestV[v]);

        best = min(best, bestV[v] + dist[V][v]);       
    }
}


    cout << best;
    return 0;
}

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