oj.uz

Submission #958186

# Submission time Handle Problem Language Result Execution time Memory
958186 2024-04-05T05:50:39 Z peterandvoi Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 3672 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;
    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 888 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 40 ms 860 KB Output is correct
4 Correct 45 ms 860 KB Output is correct
5 Correct 8 ms 604 KB Output is correct
6 Correct 8 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 64 ms 860 KB Output is correct
11 Correct 61 ms 900 KB Output is correct
12 Correct 63 ms 860 KB Output is correct
13 Correct 23 ms 860 KB Output is correct
14 Correct 28 ms 860 KB Output is correct
15 Correct 25 ms 860 KB Output is correct
16 Correct 29 ms 860 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1100 ms 3672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 856 KB Output is correct
2 Correct 9 ms 604 KB Output is correct
3 Execution timed out 1073 ms 2932 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 888 KB Output is correct
2 Correct 8 ms 604 KB Output is correct
3 Correct 40 ms 860 KB Output is correct
4 Correct 45 ms 860 KB Output is correct
5 Correct 8 ms 604 KB Output is correct
6 Correct 8 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 64 ms 860 KB Output is correct
11 Correct 61 ms 900 KB Output is correct
12 Correct 63 ms 860 KB Output is correct
13 Correct 23 ms 860 KB Output is correct
14 Correct 28 ms 860 KB Output is correct
15 Correct 25 ms 860 KB Output is correct
16 Correct 29 ms 860 KB Output is correct
17 Execution timed out 1100 ms 3672 KB Time limit exceeded
18 Halted 0 ms 0 KB -