Submission #1293661

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293661		fairkrash	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	596 ms	23764 KiB

commuter_pass

#include <bits/stdc++.h>

#include <random>

using namespace std;
using ll = long long;
using ld = long double;

ll INF = 1e18;

vector<vector<pair<ll, ll>>> g;
ll n, m;


vector<ll> dex(ll start) {
    vector<ll> dist(n, INF);
    set<pair<ll, ll>> st;
    dist[start] = 0;
    st.insert({0, start});
    while (!st.empty()) {
        ll v = st.begin()->second;
        ll mn = st.begin()->first;
        st.erase(st.begin());
        for (auto to: g[v]) {
            if (dist[to.first] > to.second + mn) {
                st.erase({dist[to.first], to.first});
                dist[to.first] = mn + to.second;
                st.insert({dist[to.first], to.first});
            }
        }
    }
    return dist;
}

vector<ll> all_good(ll start, ll p, vector<ll> &dist) {
    vector<ll> good(n, 0);
    deque<ll> q;
    q.push_back(p);
    good[p] = 1;
    good[start] = 1;
    while (!q.empty()) {
        for (auto to: g[q.front()]) {
            if (good[to.first] == 0) {
                if (dist[to.first] + to.second == dist[q.front()]) {
                    good[to.first] = 1;
                    q.push_back(to.first);
                }
            }
        }
        q.pop_front();
    }
    return good;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    g.resize(n);
    ll a, b;
    cin >> a >> b;
    ll v, u;
    cin >> v >> u;
    a--;
    b--;
    v--;
    u--;
    for (ll i = 0; i < m; i++) {
        ll v1, v2, v3;
        cin >> v1 >> v2 >> v3;
        v1--;
        v2--;
        g[v1].emplace_back(v2, v3);
        g[v2].emplace_back(v1, v3);
    }
    ll answer = INF;
    {
        vector<ll> dist = dex(a);
        vector<ll> good = all_good(a, b, dist);
        vector<ll> rast = dex(v);
        answer = min(answer, rast[u]);
        ll mn = INF;
        ll ind = INF;
        for (ll i = 0; i < good.size(); i++) {
            if (good[i] == 1) {
                if (mn > rast[i]) {
                    mn = rast[i];
                    ind = i;
                }
            }
        }
        vector<ll> cr = dex(ind);
        vector<ll> proof1 = all_good(ind, b, cr);
        vector<ll> proof2 = all_good(ind, a, cr);
        vector<ll> last = dex(u);
        for (ll i = 0; i < proof2.size(); i++) {
            if (proof2[i] == 1 || proof1[i] == 1) {
                answer = min(answer, mn + last[i]);
            }
        }
    }
    swap(u, v);
    {
        vector<ll> dist = dex(a);
        vector<ll> good = all_good(a, b, dist);
        vector<ll> rast = dex(v);
        answer = min(answer, rast[u]);
        ll mn = INF;
        ll ind = INF;
        for (ll i = 0; i < good.size(); i++) {
            if (good[i] == 1) {
                if (mn > rast[i]) {
                    mn = rast[i];
                    ind = i;
                }
            }
        }
        vector<ll> cr = dex(ind);
        vector<ll> proof1 = all_good(ind, b, cr);
        vector<ll> proof2 = all_good(ind, a, cr);
        vector<ll> last = dex(u);
        for (ll i = 0; i < proof2.size(); i++) {
            if (proof2[i] == 1 || proof1[i] == 1) {
                answer = min(answer, mn + last[i]);
            }
        }
    }
    cout << answer;
}

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