Submission #1154528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154528		54skyxenon	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	422 ms	40968 KiB

commuter_pass

// https://oj.uz/problem/view/JOI18_commuter_pass

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

#define int int64_t
#define INF INT64_MAX

typedef pair<int, int> Edge;
typedef pair<int, int> State;
typedef tuple<int, int, int, int, int> ModifiedState;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    int s, t;
    cin >> s >> t;
    s--;
    t--;

    int u, v;
    cin >> u >> v;
    u--;
    v--;

    vector<set<Edge>> graph(n);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        a--;
        b--;
        graph[a].insert({b, c});
        graph[b].insert({a, c});
    }

    auto dijkstra = [&](int source) -> vector<int> {
        vector<int> dist(n, INF);
        dist[source] = 0;

        priority_queue<State, vector<State>, greater<State>> pq;
        pq.push({0, source});

        while (pq.size()) {
            auto [curr_d, curr] = pq.top();
            pq.pop();

            if (curr_d > dist[curr]) {
                continue;
            }

            for (auto& [nei, cost] : graph[curr]) {
                int new_cost = cost + curr_d;
                if (new_cost < dist[nei]) {
                    pq.push({new_cost, nei});
                    dist[nei] = new_cost;
                }
            }
        }

        return dist;
    };

    vector<int> dist_u = dijkstra(u);
    vector<int> dist_v = dijkstra(v);

    // Modified Dijkstra with state (best, min total penalty, min u penalthy, min v penalty, node)
    priority_queue<ModifiedState, vector<ModifiedState>, greater<ModifiedState>> pq;
    vector<pair<int, int>> dist(n, {INF, INF});
    pq.push({0, dist_u[s] + dist_v[s], dist_u[s], dist_v[s], s});

    while (pq.size()) {
        auto [d, total_penalty, u_penalty, v_penalty, curr] = pq.top();
        pq.pop();

        if (pair<int, int>{d, total_penalty} > dist[curr]) {
            continue;
        }

        for (auto& [nei, cost] : graph[curr]) {
            int new_cost = cost + d;
            int new_u_penalty = min(u_penalty, dist_u[nei]);
            int new_v_penalty = min(v_penalty, dist_v[nei]);
            int new_total_penalty = min(total_penalty, new_u_penalty + new_v_penalty);
            if (pair<int, int>{new_cost, new_total_penalty} < dist[nei]) {
                pq.push({new_cost, new_total_penalty, new_u_penalty, new_v_penalty, nei});
                dist[nei] = {new_cost, new_total_penalty};
            }
        }
    }

    cout << min(dist[t].second, dist_u[v]) << '\n';
}

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45