Submission #366680

#	Time	Username	Problem	Language	Result	Execution time	Memory
366680		arbor	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	76 ms	2796 KiB

ho_t4

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
#define eb emplace_back
#define pb push_back
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
const int MN = 205, MM = 5e4 + 5;
int N, M, a[MM], b[MM], c[MM], d[MM];
vi g[MN], rg[MN];
ll dis1[2][MN], dis2[2][MN];
int from[2][MN];
bool vis[MN];
bool used[MM];

void dijk(int t, int st) {
    for (int i = 0; i <= N; i++) dis1[t][i] = 1e18, vis[i] = 0;
    dis1[t][st] = 0;
    for (int i = 0; i < N; i++) {
        int u = 0;
        for (int v = 1; v <= N; v++) {
            if (!vis[v] && dis1[t][v] < dis1[t][u]) {
                u = v;
            }
        }
        if (!u) break;
        vis[u] = 1;
        for (int e : g[u]) {
            if (u != a[e]) continue;
            int v = b[e], w = c[e];
            if (dis1[t][v] > dis1[t][u] + w) {
                dis1[t][v] = dis1[t][u] + w;
                from[t][v] = e;
            }
        }
    }
}

void rdijk(int t, int st) {
    for (int i = 0; i <= N; i++) dis2[t][i] = 1e18, vis[i] = 0;
    dis2[t][st] = 0;
    for (int i = 0; i < N; i++) {
        int u = 0;
        for (int v = 1; v <= N; v++) {
            if (!vis[v] && dis2[t][v] < dis2[t][u]) {
                u = v;
            }
        }
        if (!u) break;
        vis[u] = 1;
        for (int e : rg[u]) {
            int v = b[e], w = c[e];
            if (dis2[t][v] > dis2[t][u] + w) {
                dis2[t][v] = dis2[t][u] + w;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        g[a[i]].pb(i), rg[b[i]].pb(i);
    }
    dijk(0, 1), dijk(1, N);
    rdijk(0, N), rdijk(1, 1);
    ll ans = dis1[0][N] + dis1[1][1];
    int cur = N;
    while (from[0][cur]) {
        used[from[0][cur]] = 1;
        cur = a[from[0][cur]];
    }
    cur = 1;
    while (from[1][cur]) {
        used[from[1][cur]] = 1;
        cur = a[from[1][cur]];
    }
    for (int i = 1; i <= M; i++) {
        int u = a[i], v = b[i], w = c[i];
        if (!used[i]) {
            ll mn = dis1[0][v] + w + dis2[0][u] + dis1[1][v] + w + dis2[1][u];
            mn = min(mn, dis1[1][1] + dis1[0][v] + w + dis2[0][u]);
            mn = min(mn, dis1[0][N] + dis1[1][v] + w + dis2[1][u]);
            mn += d[i];
            ans = min(ans, mn);
        }
    }
    for (int i = 1; i <= M; i++) {
        int u = a[i], v = b[i], w = c[i];
        if (used[i]) {
            swap(a[i], b[i]);
            g[v].pb(i);
            dijk(0, 1), dijk(1, N);
            g[v].pop_back();
            swap(a[i], b[i]);
            ans = min(ans, dis1[0][N] + dis1[1][1] + d[i]);
        }
    }
    if (ans >= 1e18) ans = -1;
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:93:13: warning: unused variable 'u' [-Wunused-variable]
   93 |         int u = a[i], v = b[i], w = c[i];
      |             ^
ho_t4.cpp:93:33: warning: unused variable 'w' [-Wunused-variable]
   93 |         int u = a[i], v = b[i], w = c[i];
      |                                 ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63