Submission #1267479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267479		gay	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	909 ms	4028 KiB

ho_t4

#include <bits/stdc++.h>
#include <experimental/random>
#include <random>

using namespace std;
using ll = long long;
using ld = long double;

const ll INF = 2e18, MOD = 998244353;

void solve();

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int q = 1;
    //cin >> q;
    while (q--) {
        solve();
    }
}

struct e {
    int v, c, d, id;
};

int n, m;

vector<bool> calc(vector<vector<e>>& g, int s) {
    vector<pair<int, int>> pred(n, {-1, -1});
    vector<ll> dp(n, INF);
    dp[s] = 0;
    priority_queue<pair<ll, int>> dj;
    dj.emplace(0, s);
    while (!empty(dj)) {
        auto [w, u] = dj.top();
        dj.pop();
        w *= -1;
        if (w > dp[u]) {
            continue;
        }
        for (auto [v, c, d, id] : g[u]) {
            if (dp[v] > w + c) {
                pred[v] = {u, id};
                dp[v] = w + c;
                dj.emplace(-dp[v], v);
            }
        }
    }

    vector<bool> ans(m);
    for (int i = 0; i < n; i++) {
        if (pred[i].second != -1) {
            ans[pred[i].second] = 1;
        }
    }

    return ans;
}

vector<ll> cost(vector<vector<e>>& g, int s, int ban) {
    vector<ll> dp(n, INF);
    dp[s] = 0;
    priority_queue<pair<ll, int>> dj;
    dj.emplace(0, s);
    while (!empty(dj)) {
        auto [w, u] = dj.top();
        dj.pop();
        w *= -1;
        if (w > dp[u]) {
            continue;
        }
        for (auto [v, c, d, id] : g[u]) {
            if (id == ban) {
                continue;
            }
            if (dp[v] > w + c) {
                dp[v] = w + c;
                dj.emplace(-dp[v], v);
            }
        }
    }
    return dp;
}

void solve() {
    cin >> n >> m;
    vector<vector<e>> g(n), rev_g(n);
    vector<e> edges;
    for (int i = 0; i < m; i++) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        u--, v--;
        edges.push_back({u, v, c, d});
        g[u].push_back({v, c, d, i});
        rev_g[v].push_back({u, c, d, i});
    }

    vector<bool> dp1 = calc(g, 0);
    vector<bool> dp2 = calc(rev_g, n - 1);
    vector<bool> dp3 = calc(g, n - 1);
    vector<bool> dp4 = calc(rev_g, 0);

    vector<ll> c1 = cost(g, 0, -1);
    vector<ll> c2 = cost(rev_g, n - 1, -1);
    vector<ll> c3 = cost(g, n - 1, -1);
    vector<ll> c4 = cost(rev_g, 0, -1);

    ll ans = c1[n - 1] + c3[0];

    for (int i = 0; i < m; i++) {
        auto [u, v, w, d] = edges[i];

        ll p1 = c1[n - 1], p2 = c3[0];
        ll cnt = c1[v] + w;
        ll cnt3 = c3[v] + w;

        if (dp1[i]) {
            vector<ll> arr = cost(g, 0, i);
            p1 = arr[n - 1];
            cnt = arr[v] + w;
        }
        if (dp3[i]) {
            vector<ll> arr = cost(g, n - 1, i);
            p2 = arr[0];
            cnt3 = arr[v] + w;
        }


        if (cnt < p1) {
            ll cnt2 = c2[u];
            if (dp2[i]) {
                cnt2 = cost(rev_g, n - 1, i)[u];
            }
            p1 = min(p1, cnt + cnt2);
        }

        if (p1 + d < ans) {
            if (cnt3 < p2) {
                ll cnt2 = c4[u];
                if (dp4[i]) {
                    cnt2 = cost(rev_g, 0, i)[u];
                }
                p2 = min(p2, cnt3 + cnt2);
            }
            ans = min(ans, p1 + p2 + d);
        }
    }

    if (ans >= INF) {
        cout << -1;
        return;
    }

    cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63