Submission #680452

#	Time	Username	Problem	Language	Result	Execution time	Memory
680452		Neos	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	418 ms	26152 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define getBit(x, i) ((x) >> (i) & 1)
#define rep(i, begin, end) for (ll i = (begin); i <= (end); i++)
#define rrep(i, begin, end) for (ll i = (begin); i >= (end); i--)

typedef long long ll;
typedef pair<ll, ll> ii;

template <class T>
bool minimize(T &a, const T &b) {
    if(a > b) {a = b; return 1;}
    return 0;
}
template <class T>
bool maximize(T &a, const T &b) {
    if(a < b) {a = b; return 1;}
    return 0;
}

const int N = 1e5 + 7;

int n, m, s, t, x, y;
bool done[N];
ll d[N][4], f[N], ans = 1e18;
vector<ii> adj[N];
vector<int> dag[N];

void dijk(int s, int i) {
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    pq.push(ii(0, s)); d[s][i] = 0;

    while (sz(pq)) {
        ii u = pq.top(); pq.pop();
        if (u.fi != d[u.se][i]) continue;
        for (auto [v, w]: adj[u.se]) {
            if (minimize(d[v][i], d[u.se][i] + w)) {
                pq.push(ii(d[v][i], v));
            }
        }
    }
}

void dfs1(int u) {
    done[u] = 1; f[u] = d[u][3]; // shortest path from y->u
    for (auto [v, w]: adj[u]) if (d[u][0] + d[v][1] + w == d[t][0]) {
        if (!done[v]) dfs1(v);
        minimize(f[u], f[v]);
    }
    minimize(ans, d[u][2] + f[u]);
}

void dfs2(int u) {
    done[u] = 1; f[u] = d[u][3]; // shortest path from y->u
    for (auto [v, w]: adj[u]) if (d[u][1] + d[v][0] + w == d[t][0]) {
        if (!done[v]) dfs2(v);
        minimize(f[u], f[v]);
    }
    minimize(ans, d[u][2] + f[u]);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> s >> t >> x >> y;
    rep(i, 1, m) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb(ii(v, w)); adj[v].pb(ii(u, w));
    }

    memset(d, 0x3f, sizeof d);
    dijk(s, 0); dijk(t, 1); dijk(x, 2); dijk(y, 3);

    ans = d[y][2];
    memset(f, 0x3f, sizeof f);
    dfs1(s);
    memset(done, 0, sizeof done);
    memset(f, 0x3f, sizeof f);
    dfs2(t);
    cout << ans;
}

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