Submission #633549

#	Time	Username	Problem	Language	Result	Execution time	Memory
633549		colossal_pepe	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	664 ms	28032 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <set>
#include <tuple>
using namespace std;

using ll = long long;

const ll INF = 1e15;

int n, m, s, t, x, y;
vector<vector<pair<int, ll>>> g;

vector<ll> sssp(int start) {
    vector<ll> d(n, INF);
    set<pair<ll, int>> q;
    d[start] = 0;
    q.insert({0, start});
    while (not q.empty()) {
        auto [dist, u] = *q.begin();
        q.erase(q.begin());
        for (auto [v, w] : g[u]) {
            if (d[u] + w < d[v]) {
                q.erase({d[v], v});
                d[v] = d[u] + w;
                q.insert({d[v], v});
            }
        }
    }
    return d;
}

ll solve(vector<ll> ds, vector<ll> dt, vector<ll> to_x, vector<ll> to_y) {
    ll ans = to_x[y];
    vector<tuple<ll, ll, ll>> dp(n);
    for (int u = 0; u < n; u++) {
        auto &[dist, from_x, from_y] = dp[u];
        dist = (u == s ? 0 : INF);
        from_x = to_x[u];
        from_y = to_y[u];
    }
    set<tuple<ll, ll, ll, int>> q;
    q.insert({0, to_x[s], to_y[s], s});
    while (not q.empty()) {
        auto [dist, from_x, from_y, u] = *q.begin();
        q.erase(q.begin());
        if (ds[t] == ds[u] + dt[u]) ans = min(ans, min(from_x + to_y[u], from_y + to_x[u]));
        for (auto [v, w] : g[u]) {
            auto &[dist_v, from_x_v, from_y_v] = dp[v];
            if (dist + w < dist_v) {
                q.erase({dist_v, from_x_v, from_y_v, v});
                dist_v = dist + w;
                from_x_v = min(to_x[v], from_x);
                from_y_v = min(to_y[v], from_y);
                q.insert({dist_v, from_x_v, from_y_v, v});
            } else if (dist + w == dist_v) {
                q.erase({dist_v, from_x_v, from_y_v, v});
                from_x_v = min(from_x_v, from_x);
                from_y_v = min(from_y_v, from_y);
                q.insert({dist_v, from_x_v, from_y_v, v});
            }
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> s >> t >> x >> y;
    s--, t--, x--, y--;
    g.resize(n);
    while (m--) {
        int a, b;
        ll w;
        cin >> a >> b >> w;
        a--, b--;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    cout << solve(sssp(s), sssp(t), sssp(x), sssp(y)) << '\n';
    return 0;
}

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