Submission #958186

#	Time	Username	Problem	Language	Result	Execution time	Memory
958186		peterandvoi	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1100 ms	3672 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long

const int N = 205;
const int M = 50005;
const int INF = (int) 1e17;

int n, m;
int D[N], d[N][N];
int from[N];
int c[M], cost[M];
bool on_tree[M];
vector<pair<int, int>> g[N];
pair<int, int> edge[M];

void dijkstra(int s, int d[], vector<pair<int, int>> g[N]) {
    fill(d + 1, d + n + 1, INF);
    using T = pair<int, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    d[s] = 0;
    pq.emplace(0, s);
    while (pq.size()) {
        auto [x, u] = pq.top();
        pq.pop();
        if (d[u] == x) {
            for (auto [v, id] : g[u]) {
                if (d[v] > x + c[id]) {
                    from[v] = id;
                    pq.emplace(d[v] = x + c[id], v);
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        on_tree[from[i]] = true;
    }
}

int get_dist(int s, int t) {
    fill(D + 1, D + n + 1, INF);
    using T = pair<int, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    D[s] = 0;
    pq.emplace(0, s);
    while (pq.size()) {
        auto [x, u] = pq.top();
        pq.pop();
        if (D[u] == x) {
            for (auto [v, id] : g[u]) {
                if (D[v] > x + c[id]) {
                    pq.emplace(D[v] = x + c[id], v);
                }
            }
        }
    }
    return D[t];
}

void add(int u, int v, int id) {
    g[u].emplace_back(v, id);
}

void del(int u, int v, int id) {
    for (auto &x : g[u]) {
        if (x == make_pair(v, id)) {
            swap(x, g[u].back());
            g[u].pop_back();
            break;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n >> m;
    fill(on_tree + 1, on_tree + m + 1, true);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            d[i][j] = INF;
        }
    }
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v >> c[i] >> cost[i];
        edge[i] = {u, v};
        d[u][v] = min(d[u][v], c[i]);
        add(u, v, i);
    }
    dijkstra(1, D, g);
    dijkstra(n, D, g);
    for (int mid = 1; mid <= n; ++mid) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                d[i][j] = min(d[i][j], d[i][mid] + d[mid][j]);
            }
        }
    }
    int res = 3 * INF;
    if (d[1][n] < INF && d[n][1] < INF) {
        res = d[1][n] + d[n][1];
    }
    for (int i = 1; i <= m; ++i) {
        auto [u, v] = edge[i];
        if (on_tree[i]) {
            del(u, v, i);
            add(v, u, i);
            int A = get_dist(1, n);
            int B = get_dist(n, 1);
            if (A < INF && B < INF) {
                res = min(res, A + B + cost[i]);
            }
            del(v, u, i);
            add(u, v, i);
        } else {
            int A = min(d[1][n], d[1][v] + c[i] + d[u][n]);
            int B = min(d[n][1], d[n][v] + c[i] + d[u][1]);
            if (A < INF && B < INF) {
                res = min(res, A + B + cost[i]);
            }
        }
    }
    cout << (res == 3 * INF ? -1 : res);
}

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