Submission #1265039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265039		canhnam357	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	236 ms	16528 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N, M, S, T, U, V;
    cin >> N >> M >> S >> T >> U >> V;
    vector<vector<pair<int, int>>> adj(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    const long long inf = 1e18;
    vector<long long> ds(N + 1, inf), dt(N + 1, inf), du(N + 1, inf), dv(N + 1, inf);
    {
        ds[S] = 0;
        priority_queue<pair<long long, int>> q;
        q.emplace(0LL, S);
        while (!q.empty()) {
            auto [d, u] = q.top();
            q.pop();
            d = -d;
            if (d != ds[u]) continue;
            for (auto [v, w] : adj[u]) {
                long long nd = w + d;
                if (nd < ds[v]) {
                    ds[v] = nd;
                    q.emplace(-nd, v);
                }
            }
        }
    }
    {
        dt[T] = 0;
        priority_queue<pair<long long, int>> q;
        q.emplace(0LL, T);
        while (!q.empty()) {
            auto [d, u] = q.top();
            q.pop();
            d = -d;
            if (d != dt[u]) continue;
            for (auto [v, w] : adj[u]) {
                long long nd = w + d;
                if (nd < dt[v]) {
                    dt[v] = nd;
                    q.emplace(-nd, v);
                }
            }
        }
    }
    {
        du[U] = 0;
        priority_queue<pair<long long, int>> q;
        q.emplace(0LL, U);
        while (!q.empty()) {
            auto [d, u] = q.top();
            q.pop();
            d = -d;
            if (d != du[u]) continue;
            for (auto [v, w] : adj[u]) {
                long long nd = w + d;
                if (nd < du[v]) {
                    du[v] = nd;
                    q.emplace(-nd, v);
                }
            }
        }
    }
    {
        dv[V] = 0;
        priority_queue<pair<long long, int>> q;
        q.emplace(0LL, V);
        while (!q.empty()) {
            auto [d, u] = q.top();
            q.pop();
            d = -d;
            if (d != dv[u]) continue;
            for (auto [v, w] : adj[u]) {
                long long nd = w + d;
                if (nd < dv[v]) {
                    dv[v] = nd;
                    q.emplace(-nd, v);
                }
            }
        }
    }
    long long ans = du[V];
    vector<long long> dp1(N + 1, inf), dp2(N + 1, inf), dp3(N + 1, inf), dp4(N + 1, inf), dp5(N + 1, inf);
    vector<int> ord(N);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return ds[i] < ds[j];
    });
    {
        dp1[S] = du[S];
        for (int v : ord) {
            if (ds[v] + dt[v] != ds[T]) continue;
            for (auto [u, w] : adj[v]) {
                if (ds[u] + dt[u] != ds[T]) continue;
                if (ds[v] == w + ds[u] && dt[v] + w == dt[u]) {
                    dp1[v] = min({dp1[u], du[v], dp1[v]});
                }
            }
        }
    }
    {
        dp2[S] = dv[S];
        for (int v : ord) {
            if (ds[v] + dt[v] != ds[T]) continue;
            for (auto [u, w] : adj[v]) {
                if (ds[u] + dt[u] != ds[T]) continue;
                if (ds[v] == w + ds[u] && dt[v] + w == dt[u]) {
                    dp2[v] = min({dp2[u], dv[v], dp2[v]});
                }
            }
        }
    }
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return dt[i] < dt[j];
    });
    {
        dp4[T] = du[T];
        for (int v : ord) {
            if (ds[v] + dt[v] != ds[T]) continue;
            for (auto [u, w] : adj[v]) {
                if (ds[u] + dt[u] != ds[T]) continue;
                if (ds[v] == w + ds[u] && dt[v] + w == dt[u]) {
                    dp4[v] = min({dp4[u], du[v], dp4[v]});
                }
            }
        }
    }
    {
        dp5[T] = dv[T];
        for (int v : ord) {
            if (ds[v] + dt[v] != ds[T]) continue;
            for (auto [u, w] : adj[v]) {
                if (ds[u] + dt[u] != ds[T]) continue;
                if (ds[v] == w + ds[u] && dt[v] + w == dt[u]) {
                    dp5[v] = min({dp5[u], dv[v], dp5[v]});
                }
            }
        }
    }
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return ds[i] < ds[j];
    });
    {
        dp3[S] = dp1[S] + dp2[S];
        for (int v : ord) {
            if (ds[v] + dt[v] != ds[T]) continue;
            for (auto [u, w] : adj[v]) {
                if (ds[u] + dt[u] != ds[T]) continue;
                if (ds[v] == w + ds[u] && dt[v] + w == dt[u]) {
                    dp3[v] = min({dp1[v] + dp5[v], dp2[v] + dp4[v], dp3[u], dp3[v]});
                }
            }
        }
    }
    ans = min(ans, *min_element(dp3.begin(), dp3.end()));
    cout << ans;
    return 0;
}

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