Submission #1275536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275536		MisterReaper	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	300 ms	20280 KiB

commuter_pass

// File commuterpass.cpp created on 02.10.2025 at 20:33:44
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr i64 inf = i64(1E18);

template<typename T>
bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

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

    int N, M;
    std::cin >> N >> M;

    int S, T;
    std::cin >> S >> T;
    --S, --T;

    int U, V;
    std::cin >> U >> V;
    --U, --V;

    std::vector<std::array<int, 3>> E(M);
    std::vector<std::vector<int>> adj(N);
    for (int i = 0; i < M; ++i) {
        std::cin >> E[i][0] >> E[i][1] >> E[i][2];
        --E[i][0], --E[i][1];
        adj[E[i][0]].emplace_back(i);
        adj[E[i][1]].emplace_back(i);
    }

    i64 ans = inf;

    auto work = [&]() -> void {
        std::vector<i64> dis(N, inf), dit(N, inf);
        std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<std::pair<i64, int>>> pq;
        pq.emplace(dis[S] = 0, S);
        while (!pq.empty()) {
            auto[d, v] = pq.top();
            pq.pop();
            if (dis[v] != d) {
                continue;
            }
            for (auto e : adj[v]) {
                int u = E[e][0] ^ E[e][1] ^ v;
                if (chmin(dis[u], dis[v] + E[e][2])) {
                    pq.emplace(dis[u], u);
                }
            }
        }
        pq.emplace(dit[T] = 0, T);
        while (!pq.empty()) {
            auto[d, v] = pq.top();
            pq.pop();
            if (dit[v] != d) {
                continue;
            }
            for (auto e : adj[v]) {
                int u = E[e][0] ^ E[e][1] ^ v;
                if (chmin(dit[u], dit[v] + E[e][2])) {
                    pq.emplace(dit[u], u);
                }
            }
        }

        std::vector<std::vector<int>> zdj(N);
        for (int i = 0; i < M; ++i) {
            if (dis[E[i][0]] + dit[E[i][1]] + E[i][2] == dis[T]) {
                zdj[E[i][0]].emplace_back(E[i][1]);
            }
            if (dis[E[i][1]] + dit[E[i][0]] + E[i][2] == dis[T]) {
                zdj[E[i][1]].emplace_back(E[i][0]);
            }
        }

        dis.assign(N, inf);
        pq.emplace(dis[U] = 0, U);
        while (!pq.empty()) {
            auto[d, v] = pq.top();
            pq.pop();
            if (dis[v] != d) {
                continue;
            }
            for (auto e : adj[v]) {
                int u = E[e][0] ^ E[e][1] ^ v;
                if (chmin(dis[u], dis[v] + E[e][2])) {
                    pq.emplace(dis[u], u);
                }
            }
            for (auto u : zdj[v]) {
                if (chmin(dis[u], dis[v])) {
                    pq.emplace(dis[u], u);
                }
            }
        }

        ans = std::min(ans, dis[V]);
    };

    work();
    std::swap(S, T);
    work();

    std::cout << ans << '\n';

    return 0;
}

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