oj.uz

Submission #310860

# Submission time Handle Problem Language Result Execution time Memory
310860 2020-10-08T09:03:30 Z fishy15 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 221 ms 2432 KB 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>

#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007

#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f

// change if necessary
#define MAXN 210

using namespace std;

int n, m;
vector<array<int, 3>> adj[MAXN];
vector<array<int, 3>> radj[MAXN];
ll ans = INFLL;

ll dist_1[MAXN];
ll rdist_1[MAXN];
ll dist_n[MAXN];
ll rdist_n[MAXN];
bool vis[MAXN];

void solve(int rem) {
    memset(dist_1, 0x3f, sizeof dist_1);
    memset(rdist_1, 0x3f, sizeof dist_1);
    memset(dist_n, 0x3f, sizeof dist_n);
    memset(rdist_n, 0x3f, sizeof dist_n);
    memset(vis, 0, sizeof vis);

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, e] = pq.top();
        pq.pop();
        if (vis[e]) continue;
        vis[e] = true;
        dist_1[e] = d;
        if (e == rem) continue;
        for (auto [u, c, dd] : adj[e]) {
            if (!vis[u] && d + c < dist_1[u]) {
                pq.push({d + c, u});
                dist_1[u] = d + c;
            }
        }
    }

    memset(vis, 0, sizeof vis);
    pq.push({0, n - 1});
    while (!pq.empty()) {
        auto [d, e] = pq.top();
        pq.pop();
        if (vis[e]) continue;
        vis[e] = true;
        rdist_n[e] = d;
        for (auto [u, c, dd] : radj[e]) {
            if (!vis[u] && d + c < rdist_n[u] && u != rem) {
                pq.push({d + c, u});
                rdist_n[u] = d + c;
            }
        }
    }

    memset(vis, 0, sizeof vis);
    pq.push({0, n - 1});
    while (!pq.empty()) {
        auto [d, e] = pq.top();
        pq.pop();
        if (vis[e]) continue;
        vis[e] = true;
        dist_n[e] = d;
        if (e == rem) continue;
        for (auto [u, c, dd] : adj[e]) {
            if (!vis[u] && d + c < dist_n[u]) {
                pq.push({d + c, u});
                dist_n[u] = d + c;
            }
        }
    }

    memset(vis, 0, sizeof vis);
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, e] = pq.top();
        pq.pop();
        if (vis[e]) continue;
        vis[e] = true;
        rdist_1[e] = d;
        for (auto [u, c, dd] : radj[e]) {
            if (!vis[u] && d + c < rdist_1[u] && u != rem) {
                pq.push({d + c, u});
                rdist_1[u] = d + c;
            }
        }
    }

    ans = min(ans, dist_1[n - 1] + dist_n[0]);
    if (rem == n || adj[rem].empty()) return;

    // path without flipping
    pair<ll, ll> max_to_n = {dist_1[n - 1], dist_1[n - 1]};
    pair<ll, ll> max_to_1 = {dist_n[0], dist_n[0]};

    for (const auto &e : adj[rem]) {
        ll to_n = dist_1[rem] + e[1] + rdist_n[e[0]];
        ll to_1 = dist_n[rem] + e[1] + rdist_1[e[0]];

        if (to_n <= max_to_n.first) {
            max_to_n.second = max_to_n.first;
            max_to_n.first = to_n;
        } else if (to_n < max_to_n.second) {
            max_to_n.second = to_n;
        }

        if (to_1 <= max_to_1.first) {
            max_to_1.second = max_to_1.first;
            max_to_1.first = to_1;
        } else if (to_1 < max_to_1.second) {
            max_to_1.second = to_1;
        }
    }

    // consider flipping this
    for (const auto &e : adj[rem]) {
        ll to_n = dist_1[rem] + e[1] + rdist_n[e[0]];
        if (to_n == max_to_n.first) {
            to_n = max_to_n.second;
        } else {
            to_n = max_to_n.first;
        }
        to_n = min(to_n, dist_1[e[0]] + e[1] + rdist_n[rem]);
        to_n = min(to_n, dist_1[n - 1]);

        ll to_1 = dist_n[rem] + e[1] + rdist_1[e[0]];
        if (to_1 == max_to_1.first) {
            to_1 = max_to_1.second;
        } else {
            to_1 = max_to_1.first;
        }
        to_1 = min(to_1, dist_n[e[0]] + e[1] + rdist_1[rem]);
        to_1 = min(to_1, dist_n[0]);

        ans = min(ans, to_n + to_1 + e[2]);
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, c, d; cin >> u >> v >> c >> d;
        u--; v--;
        adj[u].push_back({v, c, d});
        radj[v].push_back({u, c, d});
    }

    for (int i = 0; i <= n; i++) {
        solve(i);
    }

    if (ans == INFLL) {
        cout << "-1\n";
    } else {
        cout << ans << '\n';
    }

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 24 ms 384 KB Output is correct
4 Correct 26 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 36 ms 472 KB Output is correct
11 Correct 35 ms 384 KB Output is correct
12 Incorrect 34 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 2432 KB Output is correct
2 Incorrect 212 ms 2428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 171 ms 1912 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 212 ms 2364 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 85 ms 2304 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 24 ms 384 KB Output is correct
4 Correct 26 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 36 ms 472 KB Output is correct
11 Correct 35 ms 384 KB Output is correct
12 Incorrect 34 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -