Submission #1073352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073352		sano	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	663 ms	41320 KiB

commuter_pass

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define shit short ll
#define pii pair<ll, ll>
#define NEK 1000000000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
#define D 8

using namespace std;

struct sr {
    ll w; pii s;
    bool operator<(const sr& other) const {
        return w < other.w;
    }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    s--; t--; u--; v--;
    vec<vec<pii>> g(n);
    For(i, m) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        g[a].push_back({ b, c });
        g[b].push_back({ a, c });
    }
    vec<ll> ds(n, -1), dt(n, -1);
    priority_queue<pii> q;
    q.push({ 0, s });
    while (!q.empty()) {
        ll som = q.top().ss; ll w = q.top().ff * (-1); q.pop();
        if (ds[som] != -1) continue;
        ds[som] = w;
        for (auto i : g[som]) {
            if (ds[i.ff] != -1) continue;
            q.push({ (-1) * (w + i.ss), i.ff });
        }
    }
    q.push({ 0, t });
    while (!q.empty()) {
        ll som = q.top().ss; ll w = q.top().ff * (-1); q.pop();
        if (dt[som] != -1) continue;
        dt[som] = w;
        for (auto i : g[som]) {
            if (dt[i.ff] != -1) continue;
            q.push({ (-1) * (w + i.ss), i.ff });
        }
    }
    ll mini = NEK;
    vec<ll> hod(n);
    For(i, n) {
        hod[i] = ds[i] + dt[i];
        mini = min(mini, ds[i] + dt[i]);
    }
    priority_queue<sr> q2;
    vec<vec<ll>> d(n, vec<ll>(3, -1));
    q2.push({ 0, { u, 1 } });
    while (!q2.empty()) {
        pii som = q2.top().s; ll w = q2.top().w * (-1); q2.pop();
        if (d[som.ff][som.ss] != -1) continue;
        d[som.ff][som.ss] = w;
        if ((som.ff == u || som.ff == v) && som.ss == 2) {
            q2.push({ (-1) * w, {som.ff, 0} });
            continue;
        }
        if (som.ss == 0) {
            for (auto i : g[som.ff]) {
                if (d[i.ff][0] != -1) continue;
                q2.push({ (-1) * (w + i.ss), { i.ff, 0 } });
            }
        }
        if(som.ss == 1) {
            for (auto i : g[som.ff]) {
                if (hod[i.ff] == mini && hod[som.ff] == mini && ((ds[som.ff] + i.ss) == ds[i.ff])) {
                    if (d[i.ff][2] == -1) {
                        q2.push({ (-1) * w, {i.ff, 2} });
                    }
                }
                if (d[i.ff][1] != -1) continue;
                q2.push({ (-1) * (w + i.ss), {i.ff, 1} });
            }
        }
        if (som.ss == 2) {
            for (auto i : g[som.ff]) {
                if (hod[i.ff] == mini && hod[som.ff] == mini && ((ds[som.ff] + i.ss) == ds[i.ff]) && d[i.ff][2] == -1) {
                    q2.push({ (-1) * w, {i.ff, 2} });
                }
                if (d[i.ff][0] != -1) continue;
                q2.push({ (-1) * (w + i.ss), {i.ff, 0} });
            }
        }
    }
    For(i, 3) if (d[v][i] == -1) d[v][i] = NEK;
    ll nasemin = NEK;
    For(i, 3) nasemin = min(nasemin, d[v][i]);
    d.clear();
    d.resize(n, vec<ll>(3, -1));
    q2.push({ 0, {v, 1} });
    while (!q2.empty()) {
        pii som = q2.top().s; ll w = q2.top().w * (-1); q2.pop();
        if (d[som.ff][som.ss] != -1) continue;
        d[som.ff][som.ss] = w;
        if ((som.ff == u || som.ff == v) && som.ss == 2) {
            q2.push({ (-1) * w, {som.ff, 0} });
            continue;
        }
        if (som.ss == 0) {
            for (auto i : g[som.ff]) {
                if (d[i.ff][0] != -1) continue;
                q2.push({ (-1) * (w + i.ss), { i.ff, 0 } });
            }
        }
        if (som.ss == 1) {
            for (auto i : g[som.ff]) {
                if (hod[i.ff] == mini && hod[som.ff] == mini && ((ds[som.ff] + i.ss) == ds[i.ff])) {
                    if (d[i.ff][2] == -1) {
                        q2.push({ (-1) * w, {i.ff, 2} });
                    }
                }
                if (d[i.ff][1] != -1) continue;
                q2.push({ (-1) * (w + i.ss), {i.ff, 1} });
            }
        }
        if (som.ss == 2) {
            for (auto i : g[som.ff]) {
                if (hod[i.ff] == mini && hod[som.ff] == mini && ((ds[som.ff] + i.ss) == ds[i.ff]) && d[i.ff][2] == -1) {
                    q2.push({ (-1) * w, {i.ff, 2} });
                }
                if (d[i.ff][0] != -1) continue;
                q2.push({ (-1) * (w + i.ss), {i.ff, 0} });
            }
        }
    }
    For(i, 3) if (d[u][i] == -1) d[u][i] = NEK;
    For(i, 3) nasemin = min(nasemin, d[u][i]);
    cout << nasemin << endl;
    return 0;
}

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