Submission #442491

#	Time	Username	Problem	Language	Result	Execution time	Memory
442491		idontreallyknow	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	411 ms	5456 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define SZ(x) ((int)((x).size()))
#define debug(x) cerr << #x << " = " << x << '\n'
const int mxn = 205, mxm = 5e4+5;
array<int,4> ed[mxm];
int n,m, ex[mxm];
vector<array<int,3>> adj[mxn], radj[mxn];
struct graph {
    ll dis[mxn], vis[mxn], pred[mxn], on[mxm];
    void dij(int rev, int s) { //to, cost, idx
        for (int q = 0; q < mxn; q++) {
            dis[q] = pred[q] = INT_MAX;
            vis[q] = 0;
        }
        for (int q = 0; q < mxm; q++) on[q] = 0;
        dis[s] = 0;
        for (int q = 0; q < n; q++) {
            int v = -1;
            for (int w = 1; w <= n; w++) {
                if (!vis[w] && (v == -1 || dis[w] < dis[v])) v = w;
            }
            if (v == -1 || dis[v] == INT_MAX) break;
            vis[v] = 1;
            if (!rev) {
                for (int w = 0; w < SZ(adj[v]); w++) {
                    if (!ex[adj[v][w][2]]) continue;
                    if (dis[v]+adj[v][w][1] < dis[adj[v][w][0]]) {
                        dis[adj[v][w][0]] = dis[v]+adj[v][w][1];
                        pred[adj[v][w][0]] = adj[v][w][2];
                    }
                }
            } else {
                for (int w = 0; w < SZ(radj[v]); w++) {
                    if (!ex[radj[v][w][2]]) continue;
                    if (dis[v]+radj[v][w][1] < dis[radj[v][w][0]]) {
                        dis[radj[v][w][0]] = dis[v]+radj[v][w][1];
                        pred[radj[v][w][0]] = radj[v][w][2];
                    }
                }
            }
        }
        for (int q = 1; q <= n; q++) if (pred[q] != INT_MAX) on[pred[q]] = 1;
    }
} g[5];
ll get(int x, int y, int i) {
    if (x == 1) {
        if (g[0].on[i]) {
            g[4].dij(0,1);
            return g[4].dis[y];
        } else return g[0].dis[y];
    } else if (x == n) {
        if (g[2].on[i]) {
            g[4].dij(0,n);
            return g[4].dis[y];
        } else return g[2].dis[y];
    } else if (y == 1) {
        if (g[1].on[i]) {
            g[4].dij(1,1);
            return g[4].dis[x];
        } else return g[1].dis[x];
    } else {
        if (g[3].on[i]) {
            g[4].dij(1,n);
            return g[4].dis[x];
        } else return g[3].dis[x];
    }
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int q = 0; q < m; q++) {
        for (int w = 0; w < 4; w++) {
            cin >> ed[q][w];
        }
        ex[q] = 1;
        adj[ed[q][0]].push_back({ed[q][1],ed[q][2],q});
        radj[ed[q][1]].push_back({ed[q][0],ed[q][2],q});
    }
    g[0].dij(0,1);
    g[1].dij(1,1);
    g[2].dij(0,n);
    g[3].dij(1,n);
    ll ans = INT_MAX;
    ans = min(ans, g[0].dis[n]+g[2].dis[1]);
    for (int q = 0; q < m; q++) {
        ex[q] = 0;
        ll a = min(get(1,n,q),get(1,ed[q][1],q)+get(ed[q][0],n,q)+ed[q][2]);
        ll b = min(get(n,1,q),get(n,ed[q][1],q)+get(ed[q][0],1,q)+ed[q][2]);
        ans = min(ans, a+b+ed[q][3]);
        ex[q] = 1;
    }
    if (ans == INT_MAX) cout << "-1\n";
    else cout << ans << '\n';
    return 0;
}

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