oj.uz

답안 #958183

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
958183 2024-04-05T05:45:58 Z peterandvoi Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 114 ms 4028 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 = 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 == 2 * INF ? -1 : res);
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 856 KB Output is correct
2 Correct 8 ms 600 KB Output is correct
3 Correct 19 ms 860 KB Output is correct
4 Correct 20 ms 892 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 9 ms 604 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 4028 KB Output is correct
2 Correct 112 ms 3672 KB Output is correct
3 Correct 107 ms 3756 KB Output is correct
4 Incorrect 16 ms 856 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 860 KB Output is correct
2 Incorrect 8 ms 604 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 856 KB Output is correct
2 Correct 8 ms 600 KB Output is correct
3 Correct 19 ms 860 KB Output is correct
4 Correct 20 ms 892 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 9 ms 604 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -