Submission #632414

#	Time	Username	Problem	Language	Result	Execution time	Memory
632414		colossal_pepe	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	874 ms	3252 KiB

ho_t4

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

using usi = unsigned int;

const usi INF = 1e8 + 1;
 
int n, m;
vector<tuple<int, int, usi, usi>> edges;
vector<vector<int>> g;
vector<vector<usi>> d;
set<int> imp_edges;
 
usi ssp(int start, int end, int flipped) {
    usi 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<usi>(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;
    usi ans;
    if (d[0][n - 1] == INF or d[n - 1][0] == INF) ans = 4294967295;
    else 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()) {
            usi x = ssp(0, n - 1, i), y = ssp(n - 1, 0, i);
            if (x != INF and y != INF) ans = min(ans, x + y + c);
            continue;
        }
        if (d[0][n - 1] != INF and d[n - 1][a] != INF and d[b][0] != INF)
            ans = min(ans, d[0][n - 1] + d[n - 1][a] + w + d[b][0] + c); // 0 1
        if (d[0][n - 1] != INF and d[n - 1][b] != INF and d[a][0] != INF)
            ans = min(ans, d[0][n - 1] + d[n - 1][b] + w + d[a][0] + c); // 0 2
        if (d[0][a] != INF and d[b][n - 1] != INF and d[n - 1][0] != INF)
            ans = min(ans, d[0][a] + w + d[b][n - 1] + d[n - 1][0] + c); // 1 0
        if (d[0][a] != INF and d[b][n - 1] != INF and d[n - 1][a] != INF and d[b][0] != INF)
            ans = min(ans, d[0][a] + w + d[b][n - 1] + d[n - 1][a] + w + d[b][0] + c); // 1 1
        if (d[0][a] != INF and d[b][n - 1] != INF and d[n - 1][b] != INF and d[a][0] != INF)
            ans = min(ans, d[0][a] + w + d[b][n - 1] + d[n - 1][b] + w + d[a][0] + c); // 1 2
        if (d[0][b] != INF and d[a][n - 1] != INF and d[n - 1][0] != INF)
            ans = min(ans, d[0][b] + w + d[a][n - 1] + d[n - 1][0] + c); // 2 0
        if (d[0][b] != INF and d[a][n - 1] != INF and d[n - 1][a] != INF and d[b][0] != INF)
            ans = min(ans, d[0][b] + w + d[a][n - 1] + d[n - 1][a] + w + d[b][0] + c); // 2 1
        if (d[0][b] != INF and d[a][n - 1] != INF and d[n - 1][b] != INF and d[a][0] != INF)
            ans = min(ans, d[0][b] + w + d[a][n - 1] + d[n - 1][b] + w + d[a][0] + c); // 2 2
    }
    if (ans == 4294967295) cout << -1 << '\n';
    else cout << ans << '\n';
    return 0;
}

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