Submission #310948

#	Time	Username	Problem	Language	Result	Execution time	Memory
310948		fishy15	Olympic Bus (JOI20_ho_t4)	C++17	37 / 100	1088 ms	2560 KiB

ho_t4

#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>

#define ll unsigned long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007

#define INF 0x3f3f3f3f
#define INFLL 0x003f3f3f3f3f3f3f

// change if necessary
#define MAXN 210

using namespace std;

int n, m;
vector<array<int, 3>> adj[MAXN];
vector<array<int, 3>> radj[MAXN];
ll ans = INFLL;

ll dist_1[MAXN];
ll rdist_1[MAXN];
ll dist_n[MAXN];
ll rdist_n[MAXN];
bool vis[MAXN];

void solve(int rem) {
    for (int i = 0; i < n; i++) {
        dist_1[i] = INFLL;
        dist_n[i] = INFLL;
        rdist_1[i] = INFLL;
        rdist_n[i] = INFLL;
    }

    memset(vis, 0, sizeof vis);

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, 0});
    int cnt = 0;
    while (!pq.empty()) {
        auto [d, e] = pq.top();
        pq.pop();
        if (vis[e]) continue;
        vis[e] = true;
        dist_1[e] = d;
        cnt++;
        if (cnt == n) break;
        if (e == rem) continue;
        for (auto [u, c, dd] : adj[e]) {
            if (!vis[u] && d + c < dist_1[u]) {
                pq.push({d + c, u});
                dist_1[u] = d + c;
            }
        }
    }

    memset(vis, 0, sizeof vis);
    pq = {};
    pq.push({0, n - 1});
    cnt = 0;
    while (!pq.empty()) {
        auto [d, e] = pq.top();
        pq.pop();
        if (vis[e]) continue;
        vis[e] = true;
        rdist_n[e] = d;
        cnt++;
        if (cnt == 0) break;
        for (auto [u, c, dd] : radj[e]) {
            if (!vis[u] && d + c < rdist_n[u] && u != rem) {
                pq.push({d + c, u});
                rdist_n[u] = d + c;
            }
        }
    }

    memset(vis, 0, sizeof vis);
    pq = {};
    pq.push({0, n - 1});
    cnt = 0;
    while (!pq.empty()) {
        auto [d, e] = pq.top();
        pq.pop();
        if (vis[e]) continue;
        vis[e] = true;
        dist_n[e] = d;
        cnt++;
        if (cnt == n) break;
        if (e == rem) continue;
        for (auto [u, c, dd] : adj[e]) {
            if (!vis[u] && d + c < dist_n[u]) {
                pq.push({d + c, u});
                dist_n[u] = d + c;
            }
        }
    }

    memset(vis, 0, sizeof vis);
    pq = {};
    pq.push({0, 0});
    cnt = 0;
    while (!pq.empty()) {
        auto [d, e] = pq.top();
        pq.pop();
        if (vis[e]) continue;
        vis[e] = true;
        rdist_1[e] = d;
        cnt++;
        if (cnt == n) break;
        for (auto [u, c, dd] : radj[e]) {
            if (!vis[u] && d + c < rdist_1[u] && u != rem) {
                pq.push({d + c, u});
                rdist_1[u] = d + c;
            }
        }
    }

    ans = min(ans, dist_1[n - 1] + dist_n[0]);
    if (rem == n || adj[rem].empty()) return;

    // path without flipping
    pair<ll, ll> max_to_n = {dist_1[n - 1], dist_1[n - 1]};
    pair<ll, ll> max_to_1 = {dist_n[0], dist_n[0]};
    pair<ll, ll> r_max_to_1 = {rdist_1[rem], rdist_1[rem]};
    pair<ll, ll> r_max_to_n = {rdist_n[rem], rdist_n[rem]};

    for (const auto &e : adj[rem]) {
        ll to_n = dist_1[rem] + e[1] + rdist_n[e[0]];
        ll to_1 = dist_n[rem] + e[1] + rdist_1[e[0]];

        if (to_n <= max_to_n.first) {
            max_to_n.second = max_to_n.first;
            max_to_n.first = to_n;
        } else if (to_n < max_to_n.second) {
            max_to_n.second = to_n;
        }

        if (to_1 <= max_to_1.first) {
            max_to_1.second = max_to_1.first;
            max_to_1.first = to_1;
        } else if (to_1 < max_to_1.second) {
            max_to_1.second = to_1;
        }

        // no flip best prev path
        ll r_to_n = e[1] + rdist_n[e[0]];
        ll r_to_1 = e[1] + rdist_1[e[0]];

        if (r_to_n <= r_max_to_n.first) {
            r_max_to_n.second = r_max_to_n.first;
            r_max_to_n.first = r_to_n;
        } else if (r_to_n < r_max_to_n.second) {
            r_max_to_n.second = r_to_n;
        }

        if (r_to_1 <= r_max_to_1.first) {
            r_max_to_1.second = r_max_to_1.first;
            r_max_to_1.first = r_to_1;
        } else if (r_to_1 < r_max_to_1.second) {
            r_max_to_1.second = r_to_1;
        }
    }

    // consider flipping this
    for (const auto &e : adj[rem]) {
        ll to_n = dist_1[rem] + e[1] + rdist_n[e[0]];
        ll r_to_n = e[1] + rdist_n[e[0]];
        if (to_n == max_to_n.first) {
            to_n = max_to_n.second;
        } else {
            to_n = max_to_n.first;
        }
        if (r_to_n == r_max_to_n.first) {
            r_to_n = r_max_to_n.second;
        } else {
            r_to_n = r_max_to_n.first;
        }
        to_n = min(to_n, dist_1[e[0]] + e[1] + r_to_n);

        ll to_1 = dist_n[rem] + e[1] + rdist_1[e[0]];
        ll r_to_1 = e[1] + rdist_1[e[0]];
        if (to_1 == max_to_1.first) {
            to_1 = max_to_1.second;
        } else {
            to_1 = max_to_1.first;
        }
        if (r_to_1 == r_max_to_1.first) {
            r_to_1 = r_max_to_1.second;
        } else {
            r_to_1 = r_max_to_1.first;
        }
        to_1 = min(to_1, dist_n[e[0]] + e[1] + r_to_1);

        ans = min(ans, to_n + to_1 + e[2]);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, c, d; cin >> u >> v >> c >> d;
        u--; v--;
        adj[u].push_back({v, c, d});
        radj[v].push_back({u, c, d});
    }

    for (int i = 0; i <= n; i++) {
        solve(i);
    }

    if (ans == INFLL) {
        cout << "-1\n";
    } else {
        cout << ans << '\n';
    }

    return 0;
}

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