Submission #563677

#	Time	Username	Problem	Language	Result	Execution time	Memory
563677		4fecta	Olympic Bus (JOI20_ho_t4)	C++17	11 / 100	64 ms	5940 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define int ll
#define ld long double
#define pii pair<int, int>
#define f first
#define s second
#define boost() cin.tie(0), cin.sync_with_stdio(0)

struct edge {
    int u, v, c, d, i;
};

const int MN = 205, MM = 50005;

int n, m, u, v, c, d, dist[MN][MN], fw[MM], bw[MM], dis[MN], vis[MN];
vector<edge> a[MN];
edge es[MM];

int dijk(int st, int ed, int blk) {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<pii, vector<pii >, greater<>> q;
    dis[st] = 0;
    q.push({0, st});
    while (q.size()) {
        pii cur = q.top();
        q.pop();
        if (cur.f > dis[cur.s]) continue;
        for (edge nxt : a[cur.s]) {
            if (nxt.i == blk) continue;
            if (dis[nxt.v] > dis[cur.s] + nxt.c) {
                dis[nxt.v] = dis[cur.s] + nxt.c;
                q.push({dis[nxt.v], nxt.v});
            }
        }
    }
    return dis[ed];
}

int32_t main() {
    boost();

    memset(dist, 0x3f, sizeof(dist));
    cin >> n >> m;
    for (int i = 1; i <= n; i++) dist[i][i] = 0;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> c >> d;
        dist[u][v] = min(dist[u][v], c);
        es[i] = {u, v, c, d, i};
        a[u].push_back({u, v, c, d, i});
    }
    for (int t = 0; t < 5; t++) {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    int ans = dist[1][n] + dist[n][1];
    if (dist[1][n] < 1e12) {
        memset(vis, 0, sizeof(vis));
        int cur = 1;
        vis[cur] = 1;
        while (cur != n) {
            bool ok = 0;
            for (edge nxt : a[cur]) {
                if (dist[1][cur] + nxt.c + dist[nxt.v][n] == dist[1][n] && !vis[nxt.v]) {
                    fw[nxt.i] = 1;
                    cur = nxt.v;
                    vis[cur] = 1;
                    ok = 1;
                    break;
                }
            }
            assert(ok);
        }
    }
    if (dist[n][1] < 1e12) {
        memset(vis, 0, sizeof(vis));
        int cur = n;
        vis[cur] = 1;
        while (cur != 1) {
            bool ok = 0;
            for (edge nxt : a[cur]) {
                if (dist[n][cur] + nxt.c + dist[nxt.v][1] == dist[n][1] && !vis[nxt.v]) {
                    bw[nxt.i] = 1;
                    cur = nxt.v;
                    vis[cur] = 1;
                    ok = 1;
                    break;
                }
            }
            assert(ok);
        }
    }
    for (int i = 1; i <= m; i++) {
        int df = dist[1][n];
        if (fw[i]) df = dijk(1, n, i);
        else df = min(df, dist[1][es[i].v] + es[i].c + dist[es[i].u][n]);
        int db = dist[n][1];
        if (bw[i]) db = dijk(n, 1, i);
        else db = min(db, dist[n][es[i].v] + es[i].c + dist[es[i].u][1]);
        ans = min(ans, df + db + es[i].d);
    }
    printf("%lld\n", ans > 1e12 ? -1 : ans);

    return 0;
}
/*
4 4
1 2 0 4
1 3 0 3
4 3 0 2
4 1 0 1
 */

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