Submission #441494

#	Time	Username	Problem	Language	Result	Execution time	Memory
441494		palilo	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	1089 ms	2524 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;

template <class T>
bool chmin(T& _old, T _new) { return _old > _new && (_old = _new, true); }
template <class T>
bool chmax(T& _old, T _new) { return _old < _new && (_old = _new, true); }

struct edge {
    int u, v;
    unsigned c, d;
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef palilo
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    constexpr unsigned INF = 0x7f7f7f7f;
    int n, m;
    cin >> n >> m;
    vector dist(n, vector(n, INF));
    for (int i = 0; i < n; ++i) {
        dist[i][i] = 0;
    }
    vector<vector<int>> adj(n);
    vector<edge> edges(m);
    {
        int eid = 0;
        for (auto& [u, v, c, d] : edges) {
            cin >> u >> v >> c >> d, --u, --v;
            chmin(dist[u][v], c);
            adj[u].emplace_back(eid++);
        }
    }
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                chmin(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    vector<bool> visited(n);
    vector<unsigned> updated_dist(n + 1); // update_dist[n] = sentinel
    auto dijk = [&](const int s, const int t) {
        fill(visited.begin(), visited.end(), false);
        fill(updated_dist.begin(), updated_dist.end(), INF);
        updated_dist[s] = 0;
        for (int _ = n; _--;) {
            int u = n;
            for (int i = 0; i < n; ++i) {
                if (!visited[i] && updated_dist[i] < updated_dist[u]) {
                    u = i;
                }
            }
            if (u == n) break;
            visited[u] = true;
            for (const auto& eid : adj[u]) {
                chmin(updated_dist[edges[eid].v], updated_dist[u] + edges[eid].c);
            }
        }
        return updated_dist[t];
    };
    const int s = 0, t = n - 1;
    unsigned ans = dist[s][t] + dist[t][s];
    int eid = 0;
    for (auto& [u, v, c, d] : edges) {
        adj[u].erase(find(adj[u].begin(), adj[u].end(), eid));
        adj[v].emplace_back(eid);
        swap(u, v);
        chmin(ans, d + dijk(s, t) + dijk(t, s));
        adj[u].pop_back();
        adj[v].emplace_back(eid);
        swap(u, v);
        ++eid;
    }
    if (ans < INF) {
        cout << ans;
    } else {
        cout << -1;
    }
}

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