Submission #632410

#	Time	Username	Problem	Language	Result	Execution time	Memory
632410		colossal_pepe	Olympic Bus (JOI20_ho_t4)	C++17	37 / 100	1034 ms	3788 KiB

ho_t4

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

using ll = long long;

const ll INF = 1e16;

int n, m;
vector<tuple<int, int, ll, ll>> edges;
vector<vector<int>> g;
vector<vector<ll>> d;
set<int> imp_edges;

ll ssp(int start, int end, int flipped) {
    ll d[n];
    for (int i = 0; i < n; i++) {
        d[i] = INF;
    }
    bool vis[n];
    memset(vis, 0, sizeof vis);
    d[start] = 0;
    for (int _ = 0; _ < n; _++) {
        int u = -1;
        for (int i = 0; i < n; i++) {
            if (not vis[i] and (u == -1 or d[i] < d[u])) u = i;
        }
        for (int i : g[u]) {
            auto [a, b, w, c] = edges[i];
            if (flipped == i) swap(a, b);
            d[b] = min(d[b], d[u] + w);
        }
        vis[u] = 1;
    }
    return d[end];
}

void restoreEdges(int u, int start, bool vis[]) {
    vis[u] = 1;
    for (int i : g[u]) {
        auto [a, b, w, c] = edges[i];
        if (not vis[b] and d[start][b] == d[start][u] + w) {
            imp_edges.insert(i);
            restoreEdges(b, start, vis);
        }
    }
}

void getImpEdges() {
    bool vis[n];
    memset(vis, 0, sizeof vis);
    restoreEdges(0, 0, vis);
    memset(vis, 0, sizeof vis);
    restoreEdges(n - 1, n - 1, vis);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    g.resize(n), edges.resize(m);
    d.resize(n, vector<ll>(n, INF));
    for (int i = 0; i < n; i++) {
        d[i][i] = 0;
    }
    for (int i = 0; i < m; i++) {
        auto &[a, b, w, c] = edges[i];
        cin >> a >> b >> w >> c;
        a--, b--;
        g[a].push_back(i);
        g[b].push_back(i);
        d[a][b] = min(d[a][b], w);
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    getImpEdges();
    // cout << "DUCK : " << endl;
    // for (int i = 0; i < n; i++) {
    //     for (int j = 0; j < n; j++) {
    //         cout << d[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    // cout << "FUCK : ";
    // for (int i : imp_edges) {
    //     cout << i << ' ';
    // }
    // cout << endl;
    ll ans = d[0][n - 1] + d[n - 1][0]; // 0 0
    for (int i = 0; i < m; i++) {
        auto [a, b, w, c] = edges[i];
        if (imp_edges.find(i) != imp_edges.end()) {
            ans = min(ans, ssp(0, n - 1, i) + ssp(n - 1, 0, i) + c);
            continue;
        }
        ans = min(ans, d[0][n - 1] + d[n - 1][a] + w + d[b][0] + c); // 0 1
        ans = min(ans, d[0][n - 1] + d[n - 1][b] + w + d[a][0] + c); // 0 2
        ans = min(ans, d[0][a] + w + d[b][n - 1] + d[n - 1][0] + c); // 1 0
        ans = min(ans, d[0][a] + w + d[b][n - 1] + d[n - 1][a] + w + d[b][0] + c); // 1 1
        ans = min(ans, d[0][a] + w + d[b][n - 1] + d[n - 1][b] + w + d[a][0] + c); // 1 2
        ans = min(ans, d[0][b] + w + d[a][n - 1] + d[n - 1][0] + c); // 2 0
        ans = min(ans, d[0][b] + w + d[a][n - 1] + d[n - 1][a] + w + d[b][0] + c); // 2 1
        ans = min(ans, d[0][b] + w + d[a][n - 1] + d[n - 1][b] + w + d[a][0] + c); // 2 2
    }
    cout << (ans < INF ? ans : -1) << '\n';
    return 0;
}

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