제출 #1275691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275691		MisterReaper	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	534 ms	22248 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;
}

template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

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<std::vector<int>> zdj(N);
        {
            std::vector<i64> dis(N, inf), dit(N, inf);
            min_pq<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);
                    }
                }
            }

            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(i);
                }
                if (dis[E[i][1]] + dit[E[i][0]] + E[i][2] == dis[T]) {
                    zdj[E[i][1]].emplace_back(i);
                }
            }

        }

        min_pq<std::tuple<i64, int, int>> pq;
        std::vector<std::array<i64, 3>> dis(N, {inf, inf, inf});
        pq.emplace(dis[U][0] = 0, U, 0);
        while (!pq.empty()) {
            auto[d, v, t] = pq.top();
            pq.pop();
            if (dis[v][t] != d) {
                continue;
            }
            if (t == 0) {
                for (auto e : adj[v]) {
                    int u = E[e][0] ^ E[e][1] ^ v;
                    if (chmin(dis[u][0], dis[v][0] + E[e][2])) {
                        pq.emplace(dis[u][0], u, 0);
                    }
                }
                if (chmin(dis[v][1], dis[v][0])) {
                    pq.emplace(dis[v][1], v, 1);
                }
                if (chmin(dis[v][2], dis[v][0])) {
                    pq.emplace(dis[v][2], v, 2);
                }
            } else if (t == 1) {
                for (auto e : zdj[v]) {
                    int u = E[e][0] ^ E[e][1] ^ v;
                    if (chmin(dis[u][1], dis[v][1])) {
                        pq.emplace(dis[u][1], u, 1);
                    }
                }
                if (chmin(dis[v][2], dis[v][1])) {
                    pq.emplace(dis[v][2], v, 2);
                }
            } else {
                for (auto e : adj[v]) {
                    int u = E[e][0] ^ E[e][1] ^ v;
                    if (chmin(dis[u][2], dis[v][2] + E[e][2])) {
                        pq.emplace(dis[u][2], u, 2);
                    }
                }
            }
        }

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

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

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

    return 0;
}

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