Submission #390781

#	Time	Username	Problem	Language	Result	Execution time	Memory
390781		timmyfeng	Olympic Bus (JOI20_ho_t4)	C++17	11 / 100	1087 ms	3148 KiB

ho_t4

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

const int N = 201, M = 50000;

int dist[N][N], depth[N], n, m;
vector<array<int, 2>> adj[N];
bool path_1[M], path_n[M];
array<int, 4> edges[M];

void find(int s, int t, bool *path) {
    int i = s;
    while (i != t) {
        int j = -1;
        while (++j < m) {
            auto [u, v, c, d] = edges[j];
            if (u == i && dist[v][t] < INT_MAX && dist[s][u] + dist[v][t] + c == dist[s][t]) {
                break;
            }
        }

        if (j == m) {
            return;
        }

        path[j] = true;
        i = edges[j][1];
    }
}

int dijkstra(int s, int t, int i) {
    fill(adj, adj + n + 1, vector<array<int, 2>>());
    fill(depth, depth + n + 1, INT_MAX);

    for (int j = 0; j < m; ++j) {
        auto [u, v, c, d] = edges[j];
        if (i == j) {
            adj[v].push_back({u, c});
        } else {
            adj[u].push_back({v, c});
        }
    }

    priority_queue<array<int, 2>> queue;
    queue.push({0, s});
    depth[0] = 0;

    while (!queue.empty()) {
        auto [d, u] = queue.top();
        queue.pop();
        d = -d;

        if (d > depth[u]) {
            continue;
        }

        for (auto [c, w] : adj[u]) {
            if (d + w < depth[c]) {
                depth[c] = d + w;
                queue.push({-depth[c], c});
            }
        }
    }

    return depth[t];
}

int calc(int s, int t, int i) {
    auto [u, v, c, d] = edges[i];
    if (max(dist[s][v], dist[u][t]) < INT_MAX) {
        return min(dist[s][t], dist[s][v] + dist[u][t] + c);
    } else {
        return dist[s][t];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            dist[i][j] = i == j ? 0 : INT_MAX;
        }
    }

    for (int i = 0; i < m; ++i) {
        auto &[u, v, c, d] = edges[i];
        cin >> u >> v >> c >> d;
        dist[u][v] = min(dist[u][v], c);
    }

    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (max(dist[i][k], dist[k][j]) < INT_MAX) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    find(1, n, path_1);
    find(n, 1, path_n);

    int ans = max(dist[1][n], dist[n][1]) < INT_MAX ? dist[1][n] + dist[n][1] : INT_MAX;

    for (int i = 0; i < m; ++i) {
        int dist_1 = path_1[i] ? dijkstra(1, n, i) : calc(1, n, i);
        int dist_n = path_n[i] ? dijkstra(n, 1, i) : calc(n, 1, i);
        if (max(dist_1, dist_n) < INT_MAX) {
            ans = min(ans, dist_1 + dist_n + edges[i][3]);
        }
    }

    cout << (ans < INT_MAX ? ans : -1) << "\n";
}

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