Submission #704836

#	Time	Username	Problem	Language	Result	Execution time	Memory
704836		prarie	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	1081 ms	3860 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF = 1E12;

vector<ll> dijkstra(int N, int start, vector<vector<ll>> &adj) {
    vector<ll> dist(N, INF);
    vector<int> check(N, 0);
    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 (int nxt = 0; nxt < N; nxt++) {
            if (dist[nxt] > dist[cur] + adj[cur][nxt]) {
                dist[nxt] = dist[cur] + adj[cur][nxt];
            }
        }
    }
    return dist;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int N, M;
    cin >> N >> M;
    vector<array<ll, 4>> adj(M);
    vector<vector<ll>> adj_mat(N, vector<ll>(N, INF));
    vector<vector<ll>> rev_mat(N, vector<ll>(N, INF));
    for (auto &[x, y, z, w] : adj) {
        cin >> x >> y >> z >> w;
        x--; y--;
        adj_mat[x][y] = min(adj_mat[x][y], z);
        rev_mat[y][x] = min(rev_mat[y][x], z);
    }
    for (int i = 0; i < N; i++) {
        adj_mat[i][i] = rev_mat[i][i] = 0;
    }

    // dist0 : 0 -> i
    // dist1 : N - 1 - > i
    // dist2 : i -> 0
    // dist3 : i -> N - 1
    auto dist0 = dijkstra(N, 0, adj_mat);
    auto dist1 = dijkstra(N, N - 1, adj_mat);
    auto dist2 = dijkstra(N, 0, rev_mat);
    auto dist3 = dijkstra(N, N - 1, rev_mat);
    map<array<ll, 3>, int> shortest_path;
    int ed = N - 1;
    while (1) {
        bool changed = 0;
        for (int i = 0; i < N; i++) {
            if (i == ed) {
                continue;
            }
            if (dist0[i] + adj_mat[i][ed] == dist0[ed]) {
                shortest_path[{ i, ed, adj_mat[i][ed] }] = 0;
                ed = i;
                changed = 1;
                break;
            }
        }
        if (!changed) {
            break;
        }
    }
    ed = 0;
    while (1) {
        bool changed = 0;
        for (int i = 0; i < N; i++) {
            if (i == ed) {
                continue;
            }
            if (dist1[i] + adj_mat[i][ed] == dist1[ed]) {
                shortest_path[{ i, ed, adj_mat[i][ed] }] = 0;
                ed = i;
                changed = 1;
                break;
            }
        }
        if (!changed) {
            break;
        }
    }
    const ll ML = 1200000005;
    ll ans = dist0[N - 1] + dist1[0];
    for (int i = 0; i < M; i++) {
        auto &[u, v, cst, inv] = adj[i];
        if (shortest_path.count({ u, v, cst }) && shortest_path[{ u, v, cst }] == 0) {
            shortest_path[{ u, v, cst }] = 1;
            swap(u, v);
            vector<vector<ll>> new_adj(N, vector<ll>(N, INF));
            for (int e = 0; e < M; e++) {
                new_adj[adj[e][0]][adj[e][1]] = min(new_adj[adj[e][0]][adj[e][1]], adj[e][2]);
            }
            for (int i = 0; i < N; i++) {
                new_adj[i][i] = 0;
            }
            auto p = dijkstra(N, 0, new_adj);
            auto q = dijkstra(N, N - 1, new_adj);
            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