Submission #1259297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259297		wedonttalkanymore	Olympic Bus (JOI20_ho_t4)	C++20	5 / 100	1095 ms	3400 KiB

ho_t4

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>

using namespace std;
using ll = long long;

const ll inf = 1e15;

struct Edge {
    int v;
    ll c;
    int id;
};

struct InputEdge {
    int u, v;
    ll c, d;
};

vector<InputEdge> edges;
vector<vector<Edge>> base_adj;
int n, m;

vector<ll> dijkstra_modified(int start, int remove_id, InputEdge add_edge) {
    vector<ll> dist(n+1, inf);
    vector<bool> visited(n+1, false);
    dist[start] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;
        visited[u] = true;

        if (remove_id == -1) {
            for (const Edge& e : base_adj[u]) {
                ll nd = d + e.c;
                if (nd < dist[e.v]) {
                    dist[e.v] = nd;
                    pq.push({nd, e.v});
                }
            }
        } else {
            if (u == add_edge.u) {
                for (const Edge& e : base_adj[u]) {
                    if (e.id == remove_id) continue;
                    ll nd = d + e.c;
                    if (nd < dist[e.v]) {
                        dist[e.v] = nd;
                        pq.push({nd, e.v});
                    }
                }
            } else if (u == add_edge.v) {
                for (const Edge& e : base_adj[u]) {
                    ll nd = d + e.c;
                    if (nd < dist[e.v]) {
                        dist[e.v] = nd;
                        pq.push({nd, e.v});
                    }
                }
                ll nd = d + add_edge.c;
                if (nd < dist[add_edge.u]) {
                    dist[add_edge.u] = nd;
                    pq.push({nd, add_edge.u});
                }
            } else {
                for (const Edge& e : base_adj[u]) {
                    ll nd = d + e.c;
                    if (nd < dist[e.v]) {
                        dist[e.v] = nd;
                        pq.push({nd, e.v});
                    }
                }
            }
        }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    base_adj.resize(n+1);
    edges.resize(m);

    for (int i = 0; i < m; i++) {
        int u, v;
        ll c, d;
        cin >> u >> v >> c >> d;
        edges[i] = {u, v, c, d};
        base_adj[u].push_back({v, c, i});
    }

    vector<ll> dist_forward0 = dijkstra_modified(1, -1, {0,0,0,0});
    vector<ll> dist_backward0 = dijkstra_modified(n, -1, {0,0,0,0});
    ll total0 = inf;
    if (dist_forward0[n] < inf && dist_backward0[1] < inf) {
        total0 = dist_forward0[n] + dist_backward0[1];
    }

    ll ans = total0;

    for (int i = 0; i < m; i++) {
        InputEdge e = edges[i];
        vector<ll> dist_forward = dijkstra_modified(1, i, e);
        vector<ll> dist_backward = dijkstra_modified(n, i, e);
        if (dist_forward[n] < inf && dist_backward[1] < inf) {
            ll total_i = dist_forward[n] + dist_backward[1] + e.d;
            if (total_i < ans) {
                ans = total_i;
            }
        }
    }

    if (ans >= inf) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

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