Submission #916144

#	Time	Username	Problem	Language	Result	Execution time	Memory
916144		Amirreza_Fakhri	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	741 ms	29220 KiB

commuter_pass

// In the name of the God
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;

const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 1e5+5;

int n, m, s, t, x, y, ans, dist[4][maxn], mn[2][maxn], cnt[maxn];
vector <pii> adj[maxn];
set <pii> st;

void dij1(int v, int i) {
    memset(dist[i], 63, sizeof dist[i]);
    st.insert(mp(0, v));
    while (st.size()) {
        int u = st.begin() -> S, d = st.begin() -> F;
        st.erase(st.begin());
        if (dist[i][u] <= d) continue;
        dist[i][u] = d;
        cnt[u]++;
        for (pii e : adj[u]) st.insert(mp(e.S+d, e.F));
    }
}

void dij2() {
    memset(dist[0], 63, sizeof dist[0]);
    memset(mn, 63, sizeof mn);
    st.insert(mp(0, s));
    while (st.size()) {
        int u = st.begin() -> S, d = st.begin() -> F;
        st.erase(st.begin());
        if (dist[0][u] <= d) continue;
        dist[0][u] = d;
        smin(mn[0][u], dist[2][u]);
        smin(mn[1][u], dist[3][u]);
        if (d+dist[1][u] == dist[1][s]) {
            smin(ans, mn[0][u]+dist[3][u]);
            smin(ans, mn[1][u]+dist[2][u]);
        }
        cnt[u]++;
        for (pii e : adj[u]) {
            if (e.S+d+dist[1][e.F] == dist[1][s]) {
                smin(mn[0][e.F], mn[0][u]);
                smin(mn[1][e.F], mn[1][u]);
                st.insert(mp(e.S+d, e.F));
            }
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> s >> t >> x >> y;
    s--, t--, x--, y--;
    for (int i = 0; i < m; i++) {
        int v, u, w; cin >> v >> u >> w;
        adj[--v].pb(mp(--u, w));
        adj[u].pb(mp(v, w));
    }
    dij1(t, 1), dij1(x, 2), dij1(y, 3);
    ans = dist[2][y];
    dij2();
    for (int i = 0; i < n; i++) assert(cnt[i] <= 4);
    cout << ans << '\n';
    return 0;
}

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