Submission #860203

#	Time	Username	Problem	Language	Result	Execution time	Memory
860203		Pring	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	459 ms	5872 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fs first
#define sc second
#define mp make_pair
typedef pair<int, int> pii;

struct EDGE {
    int u, v, c, d, is_tree[2], id;
    EDGE() {}
};

const int MXN = 205, MXM = 50005, INF = 3000000000000000000;
int n, m, dis1[MXN], dis1_inv[MXN], disn[MXN], disn_inv[MXN], p[MXN], dis[MXN];
vector<int> v[MXN][MXN];
EDGE edge[MXM];
bitset<MXN> b;

inline void DIJKSTRA(int sr, int *dis, int id, int inv) {
    b.reset();
    fill(dis + 1, dis + n + 1, INF);
    fill(p + 1, p + n + 1, 0);
    dis[sr] = 0;
    for (int $ = 0; $ < n; $++) {
        int x = -1;
        for (int i = 1; i <= n; i++) {
            if (b[i]) continue;
            if (x == -1) x = i;
            else if (dis[x] > dis[i]) x = i;
        }
        // if (x == -1) cout << "ERROR" << endl;
        // cout << "x: " << x << endl;
        b[x] = true;
        if (id != -1) edge[p[x]].is_tree[id] = true;
        for (int j = 1; j <= n; j++) for (auto i : v[x][j]) {
            if (inv) {
                if (i > 0) continue;
                i *= -1;
            } else {
                if (i < 0) continue;
            }
            // if (b[i]) continue;
            if (dis[x] + edge[i].c < dis[j]) {
                dis[j] = dis[x] + edge[i].c;
                p[j] = i;
            }
        }
    }
}

inline int SOLVE_1(int id) {
    if (edge[id].is_tree[0]) {
        DIJKSTRA(1, dis, -1, false);
        return dis[n];
    }
    return min(dis1[n], dis1[edge[id].u] + edge[id].c + disn_inv[edge[id].v]);
}

inline int SOLVE_n(int id) {
    if (edge[id].is_tree[1]) {
        DIJKSTRA(n, dis, -1, false);
        return dis[1];
    }
    return min(disn[1], disn[edge[id].u] + edge[id].c + dis1_inv[edge[id].v]);
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> edge[i].u >> edge[i].v >> edge[i].c >> edge[i].d;
        edge[i].id = v[edge[i].u][edge[i].v].size();
        v[edge[i].u][edge[i].v].push_back(i);
        v[edge[i].v][edge[i].u].push_back(-i);
    }
    DIJKSTRA(1, dis1, 0, false);
    DIJKSTRA(1, dis1_inv, -1, true);
    DIJKSTRA(n, disn, 1, false);
    DIJKSTRA(n, disn_inv, -1, true);
    // for (int i = 1; i <= m; i++) cout << edge[i].is_tree[1];
    // cout << endl;
    // return 0;
    int x = dis1[n] + disn[1];
    for (int i = 1; i <= m; i++) {
        swap(edge[i].u, edge[i].v);
        v[edge[i].u][edge[i].v][edge[i].id] *= -1;
        v[edge[i].v][edge[i].u][edge[i].id] *= -1;
        x = min(x, edge[i].d + SOLVE_1(i) + SOLVE_n(i));
        swap(edge[i].u, edge[i].v);
        v[edge[i].u][edge[i].v][edge[i].id] *= -1;
        v[edge[i].v][edge[i].u][edge[i].id] *= -1;
    }
    cout << (x >= INF ? -1LL : x) << endl;
    return 0;
}

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