oj.uz

Submission #958185

# Submission time Handle Problem Language Result Execution time Memory
958185 2024-04-05T05:47:47 Z peterandvoi Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 115 ms 4620 KB 
#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;
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 860 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 19 ms 856 KB Output is correct
4 Correct 23 ms 860 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 8 ms 828 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Incorrect 1 ms 560 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 3760 KB Output is correct
2 Correct 112 ms 3672 KB Output is correct
3 Correct 115 ms 3760 KB Output is correct
4 Incorrect 16 ms 860 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 856 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 67 ms 3716 KB Output is correct
4 Correct 8 ms 600 KB Output is correct
5 Correct 84 ms 4496 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 32 ms 4444 KB Output is correct
9 Correct 39 ms 4444 KB Output is correct
10 Correct 61 ms 4444 KB Output is correct
11 Correct 56 ms 4620 KB Output is correct
12 Correct 70 ms 4472 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 476 KB Output is correct
16 Incorrect 0 ms 344 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 860 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 19 ms 856 KB Output is correct
4 Correct 23 ms 860 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 8 ms 828 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Incorrect 1 ms 560 KB Output isn't correct
10 Halted 0 ms 0 KB -