Submission #704859

#	Time	Username	Problem	Language	Result	Execution time	Memory
704859		prarie	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	56 ms	4548 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF = 1E12;
int used[50505];
vector<array<int, 4>> edges;

vector<ll> dijkstra(int N, int start, vector<vector<array<int, 4>>> &adj, int p = 0) {
    vector<ll> dist(N, INF);
    vector<int> check(N, 0);
    vector<int> prv(N, -1);
    dist[start] = 0;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> pq;
    for (int rep = 0; rep < N; rep++) {
        int cur = -1;
        ll totalCost = INF;
        for (int i = 0; i < N; i++) {
            if (!check[i] && dist[i] < totalCost) {
                cur = i;
                totalCost = dist[i];
            }
        }
        if (cur == -1) {
            break;
        }
        check[cur] = 1;

        for (auto &[nxt, cst, _, idx] : adj[cur]) {
            if (dist[nxt] > dist[cur] + cst) {
                dist[nxt] = dist[cur] + cst;
                prv[nxt] = idx;
            }
        }
    }

    if (p && dist[N - 1 - start] != INF) {
        for (int cur = N - 1 - start; prv[cur] != -1; cur = edges[prv[cur]][0]) {
            used[prv[cur]] = 1;
        }
    }

    return dist;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int N, M;
    cin >> N >> M;
    vector<vector<array<int, 4>>> adj(N), rev(N);
    for (int i = 0; i < M; i++) {
        int x, y, z, w;
        cin >> x >> y >> z >> w;
        x--; y--;
        edges.push_back({ x, y, z, w });
        adj[x].push_back({ y, z, w, i });
        rev[y].push_back({ x, z, w, i });
    }

    // dist0 : 0 -> i
    // dist1 : N - 1 - > i
    // dist2 : i -> 0
    // dist3 : i -> N - 1
    auto dist0 = dijkstra(N, 0, adj, 1);
    auto dist1 = dijkstra(N, N - 1, adj, 1);
    auto dist2 = dijkstra(N, 0, rev);
    auto dist3 = dijkstra(N, N - 1, rev);
    const ll ML = 1200000000;
    ll ans = dist0[N - 1] + dist1[0];
    for (int i = 0; i < M; i++) {
        auto &[u, v, cst, inv] = edges[i];
        if (used[i]) {
            adj[u].erase(find_if(adj[u].begin(), adj[u].end(), [&](const array<int, 4> &x) {
                return x[3] == i;
            }));
            adj[v].push_back({ u, cst, inv, i });
            auto p = dijkstra(N, 0, adj);
            auto q = dijkstra(N, N - 1, adj);
            adj[u].push_back({ v, cst, inv, i });
            adj[v].erase(find_if(adj[v].begin(), adj[v].end(), [&](const array<int, 4> &x) {
                return x[3] == i;
            }));
            ans = min(ans, p[N - 1] + q[0] + inv);
            continue;
        }
        int c_ = cst + inv;
        ans = min(ans, min(dist0[N - 1], dist0[v] + dist3[u] + c_) + min(dist1[v] + dist2[u] + c_, dist1[0]));
    }

    if (ans > ML) {
        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