제출 #1314766

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1314766		layk	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	735 ms	110748 KiB

commuter_pass

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <immintrin.h>

#ifndef DEBUG
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#endif

using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;
//
using ld = long double;
using ll = long long;
using i128 = __int128;
using ull = unsigned long long;
using pll = std::pair<ll, ll>;
using cmpl = std::complex<ld>;
template<typename T>
using oset = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;

constexpr ll MOD1 = 998244353;
constexpr ll MOD = 1000000007;
constexpr ll INV2 = 499122177;
constexpr ld PI = 3.141592653589793;
const ld eps = 1e-7;
const ll K = 500;
//const ll C = 200;

std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());

ld START_TIME = clock();

std::vector<ll> d, d1;

void Deikstr(ll str, std::vector<std::vector<pll>> &G) {
    std::set<pll> q;
    q.insert({0, str});
    d[str] = 0;
    while (!q.empty()) {
        auto [dst, v] = *q.begin();
        q.erase(q.begin());
        for (auto [u, w]: G[v]) {
            if (dst + w < d[u]) {
                q.erase({d[u], u});
                d[u] = dst + w;
                q.insert({d[u], u});
            }
        }
    }
}

void Deikstr1(ll str, std::vector<std::vector<pll>> &G) {
    std::set<pll> q;
    q.insert({0, str});
    d1.assign(G.size(), 1e18);
    d1[str] = 0;
    while (!q.empty()) {
        auto [dst, v] = *q.begin();
        q.erase(q.begin());
        for (auto [u, w]: G[v]) {
            if (dst + w < d1[u]) {
                q.erase({d1[u], u});
                d1[u] = dst + w;
                q.insert({d1[u], u});
            }
        }
    }
}

void solve() {
    ll n, m;
    ll s, t, u, v;
    std::cin >> n >> m;
    std::cin >> s >> t;
    --s, --t;
    std::cin >> u >> v;
    --u, --v;
    std::vector<std::vector<pll>> G;
    G.resize(n);
    d.resize(n, 1e18);
    d1.resize(n, 1e18);
    for (int i = 0; i < m; ++i) {
        ll v1, u1, w;
        std::cin >> v1 >> u1 >> w;
        --v1, --u1;
        G[v1].push_back({u1, w});
        G[u1].push_back({v1, w});
    }
    Deikstr(s, G);
    Deikstr1(t, G);
    std::vector<std::vector<pll>> G1(3 * n), G2(3 * n);
    for (int i = 0; i < n; ++i) {
        for (auto [uu, w]: G[i]) {
            if (d[i] + w + d1[uu] == d[t]) {
                G1[i].push_back({uu + n, 0});
                G1[i].push_back({uu + 2 * n, 0});
                G1[i + n].push_back({uu + 2 * n, 0});
                G1[i + n].push_back({uu + n, 0});
                G2[uu].push_back({i + n, 0});
                G2[uu].push_back({i + 2 * n, 0});
                G2[uu + n].push_back({i + 2 * n, 0});
                G2[uu + n].push_back({i + n, 0});
            }
        }
    }
    for (ll i = 0; i < n; ++i) {
        for (auto &[uu, w]: G[i]) {
            G1[i].push_back({uu, w});
            G1[i + 2 * n].push_back({uu + 2 * n, w});
            G2[i].push_back({uu, w});
            G2[i + 2 * n].push_back({uu + 2 * n, w});
        }
    }
    Deikstr1(v, G1);
    ll ans = std::min({d1[u], d1[u + n], d1[u + 2 * n]});
    Deikstr1(v, G2);
    ans = std::min({ans, d1[u], d1[u + n], d1[u + 2 * n]});
    std::cout << ans;
}

signed main() {
#ifdef DEBUG
    std::freopen("/home/anton/CLionProjects/untitled/input.txt", "r", stdin);
#else
    //    std::freopen("tri.in", "r", stdin); std::freopen("tri.out", "w", stdout);
#endif
    std::cin.tie(nullptr)->std::ios_base::sync_with_stdio(false);
    int tt = 1;
    //    ll g; std::cin >> g;
//    std::cin >> tt;
    while (tt--) {
        solve();
    }
#ifdef DEBUG
    std::cerr << '\n';
    ld TIME = (clock() - START_TIME) / CLOCKS_PER_SEC;
    std::cerr << "Time: " << TIME << '\n';
#endif
}

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