Submission #310867

# Submission time Handle Problem Language Result Execution time Memory
310867 2020-10-08T09:39:25 Z fishy15 Olympic Bus (JOI20_ho_t4) C++14
0 / 100
217 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 0x003f3f3f3f3f3f3f

// 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) {
    for (int i = 0; i < n; i++) {
        dist_1[i] = INFLL;
        dist_n[i] = INFLL;
        rdist_1[i] = INFLL;
        rdist_n[i] = INFLL;
    }

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

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

Compilation message

ho_t4.cpp: In function 'void solve(int)':
ho_t4.cpp:52:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |         auto [d, e] = pq.top();
      |              ^
ho_t4.cpp:58:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |         for (auto [u, c, dd] : adj[e]) {
      |                   ^
ho_t4.cpp:69:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |         auto [d, e] = pq.top();
      |              ^
ho_t4.cpp:74:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |         for (auto [u, c, dd] : radj[e]) {
      |                   ^
ho_t4.cpp:85:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |         auto [d, e] = pq.top();
      |              ^
ho_t4.cpp:91:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |         for (auto [u, c, dd] : adj[e]) {
      |                   ^
ho_t4.cpp:102:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |         auto [d, e] = pq.top();
      |              ^
ho_t4.cpp:107:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  107 |         for (auto [u, c, dd] : radj[e]) {
      |                   ^
# 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 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 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 384 KB Output is correct
11 Correct 35 ms 384 KB Output is correct
12 Incorrect 35 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 217 ms 2304 KB Output is correct
2 Incorrect 217 ms 2432 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 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 168 ms 1784 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 213 ms 2296 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Incorrect 79 ms 2176 KB Output isn't correct
9 Halted 0 ms 0 KB -
# 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 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 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 384 KB Output is correct
11 Correct 35 ms 384 KB Output is correct
12 Incorrect 35 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -