Submission #1297388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297388		baotoan655	Olympic Bus (JOI20_ho_t4)	C++20	100 / 100	256 ms	2048 KiB

ho_t4

#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

const int inf = 1e9 + 7;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

//    file("A") else file("task");

    int n, m;
    cin >> n >> m;
    vector<vector<int>> dist(n, vector<int>(n, inf));
    for(int i = 0; i < n; ++i) dist[i][i] = 0;
    vector<array<int, 4>> ed(m);
    vector<vector<pair<int, int>>> g(n);
    for(int i = 0; i < m; ++i) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        --u, --v;
        ed[i] = {u, v, c, d};
        dist[u][v] = min(dist[u][v], c);
        g[u].emplace_back(v, i);
    }
    for(int k = 0; k < n; ++k) {
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < n; ++j) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
    long long ans = dist[0][n - 1] + dist[n - 1][0];
    auto dij = [&](int s, int e, int v) {
        vector<int> d(n, inf), used(n);
        priority_queue<pair<int, int>> pq;
        pq.emplace(0, s);
        d[s] = 0;
        while (!pq.empty()) {
            int x = pq.top().second;
            pq.pop();
            if (x == e) break;
            if (used[x]++) continue;
            for (auto i : g[x]) {
                int u = i.first, z = i.second;
                if (z == v) continue;
                if (d[u] > d[x] + ed[z][2]) {
                    d[u] = d[x] + ed[z][2];
                    pq.emplace(-d[u], u);
                }
            }
            if (x == ed[v][1]) {
                if (d[ed[v][0]] > d[x] + ed[v][2]) {
                    d[ed[v][0]] = d[x] + ed[v][2];
                    pq.emplace(-d[ed[v][0]], ed[v][0]);
                }
            }
        }
        return d[e];
    };
    for(int i = 0; i < m; ++i) {
        int u = ed[i][0], v = ed[i][1], c = ed[i][2], d = ed[i][3];
        long long a = min(dist[0][n - 1], dist[0][v] + dist[u][n - 1] + c);
        long long b = min(dist[n - 1][0], dist[n - 1][v] + dist[u][0] + c);
        if (a + b + d < ans) {
            long long x = dij(0, n - 1, i);
            long long y = dij(n - 1, 0, i);
            ans = min(ans, x + y + d);
        }
    }
    if(ans >= inf) ans = -1;
    cout << ans << '\n';
    return 0;
}

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