Submission #286589

#	Time	Username	Problem	Language	Result	Execution time	Memory
286589		valerikk	Olympic Bus (JOI20_ho_t4)	C++11	0 / 100	27 ms	7296 KiB

ho_t4

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

const int N = 205, M = 5e4 + 7;
const int INF = 1e18 + 39;
struct Edge{
    int v, u, c, d;
    Edge() {}
    Edge(int v, int u, int c, int d) : v(v), u(u), c(c), d(d) {}
};

int n ,m;
Edge edg[M];

void dijks(int st, vector<int>& d, vector<int>& p, bool rev, const vector<vector<int>>& g, int ign) {
    for (int i = 0; i < n; i++) {
        d[i] = INF;
        p[i] = -1;
    }
    d[st] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push({d[st], st});
    while (!q.empty()) {
        auto cur = q.top();
        q.pop();
        int v = cur.second;
        if (d[v] != cur.first)
            continue;
        for (auto id : g[v]) {
            int w = edg[id].c, u = rev ? edg[id].v : edg[id].u;
            if (d[v] + w < d[u]) {
                d[u] = d[v] + w;
                p[u] = id;
                q.push({d[u], u});
            }
        }
    }
}

vector<vector<int>> g(N), gr(N);
vector<int> d1(N), dn(N);
vector<int> d1r(N), dnr(N);
vector<int> p1(N), pn(N);
vector<int> p1r(N), pnr(N);
bool bad1[N], badn[N];
bool bad1r[N], badnr[N];
vector<int> tmp_d(N), tmp_p(N);

int get_d1(int v, int ign) {
    if (bad1[ign]) {
        dijks(0, tmp_d, tmp_p, 0, g, ign);
        return tmp_d[v];
    }
    return d1[v];
}

int get_dn(int v, int ign) {
    if (badn[ign]) {
        dijks(n - 1, tmp_d, tmp_p, 0, g, ign);
        return tmp_d[v];
    }
    return dn[v];
}

int get_d1r(int v, int ign) {
    if (bad1r[ign]) {
        dijks(0, tmp_d, tmp_p, 1, gr, ign);
        return tmp_d[v];
    }
    return d1r[v];
}

int get_dnr(int v, int ign) {
    if (badnr[ign]) {
        dijks(n - 1, tmp_d, tmp_p, 1, gr, ign);
        return tmp_d[v];
    }
    return dnr[v];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> edg[i].v >> edg[i].u >> edg[i].c >> edg[i].d;
        edg[i].v--;
        edg[i].u--;
        g[edg[i].v].push_back(i);
        gr[edg[i].u].push_back(i);
    }
    dijks(0, d1, p1, 0, g, -1);
    dijks(0, d1r, p1r, 1, gr, -1);
    dijks(n - 1, dn, pn, 0, g, -1);
    dijks(n - 1, dnr, pnr, 1, gr, -1);
    for (int i = 0; i < n; i++) {
        if (~p1[i])
            bad1[p1[i]] = 1;
        if (~pn[i])
            badn[pn[i]] = 1;
        if (~p1r[i])
            bad1r[p1r[i]] = 1;
        if (~pnr[i])
            badnr[pnr[i]] = 1;
    }
    int ans = min(INF, d1[n - 1] + dn[0]);
    for (int i = 0; i < m; ++i) {
        int dist1 = min(get_d1(n - 1, i), get_d1(edg[i].u, i) + get_dnr(edg[i].v, i) + edg[i].c);
        int distn = min(get_dn(0, i), get_dn(edg[i].u, i) + get_d1r(edg[i].v, i) + edg[i].c);
        ans = min(ans, dist1 + distn + edg[i].d);
    }
    if (ans == INF)
        cout << "-1\n";
    else
        cout << ans << '\n';
    return 0;
}

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