oj.uz

Submission #310857

# Submission time Handle Problem Language Result Execution time Memory
310857 2020-10-08T08:57:46 Z fishy15 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 216 ms 3448 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<int, int>, vector<pair<int, int>>, greater<pair<int, 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;
            }
        }
    }

    /* cout << "rem " << rem << '\n'; */
    /* for (int i = 0; i < n; i++) { */
    /*     cout << dist_1[i] << ' '; */
    /* } */
    /* cout << '\n'; */
    /* for (int i = 0; i < n; i++) { */
    /*     cout << dist_n[i] << ' '; */
    /* } */
    /* cout << '\n'; */
    /* for (int i = 0; i < n; i++) { */
    /*     cout << rdist_1[i] << ' '; */
    /* } */
    /* cout << '\n'; */
    /* for (int i = 0; i < n; i++) { */
    /*     cout << rdist_n[i] << ' '; */
    /* } */
    /* cout << '\n'; */

    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;
        }
    }

    /* cout << "rem " << rem << '\n'; */
    /* cout << max_to_n.first<< ' ' << max_to_n.second << '\n'; */
    /* cout << max_to_1.first<< ' ' << max_to_1.second << '\n'; */

    // 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]);

        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]);

        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 512 KB Output is correct
4 Correct 26 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 35 ms 504 KB Output is correct
11 Correct 35 ms 504 KB Output is correct
12 Incorrect 34 ms 468 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 3448 KB Output is correct
2 Incorrect 216 ms 3448 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 174 ms 2552 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 215 ms 3204 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Incorrect 82 ms 3200 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 512 KB Output is correct
4 Correct 26 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 35 ms 504 KB Output is correct
11 Correct 35 ms 504 KB Output is correct
12 Incorrect 34 ms 468 KB Output isn't correct
13 Halted 0 ms 0 KB -