제출 #701630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
701630		phi	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	1286 ms	262144 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <tuple>
#include <cmath>

using namespace std;

vector<long long> min_dist(vector<vector<pair<int, long long>>> &adj, int source, int n) {
    vector<long long> depth(n, -1);

    using T = pair<long long, int>;
    priority_queue<T, vector<T>, greater<T>> q;
    q.push({ 0, source });

    while (!q.empty()) {
        auto [ d, v ] = q.top();
        q.pop();

        if (depth[v] != -1) continue;
        depth[v] = d;

        for (auto [ u, w ] : adj[v]) {
            q.push({ d + w, u });
        }
    }

    return depth;
}

struct Path {
    int current;
    long long cost;
    long long u_dist;
    long long v_dist;

    friend bool operator>(const Path &l, const Path &r) {
        if (l.cost == r.cost) {
            return (l.u_dist + l.v_dist) > (r.u_dist + r.v_dist);
        }
        return l.cost > r.cost;
    }
};

int main() {
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    s--; t--; u--; v--;

    vector<vector<pair<int, long long>>> adj(n);

    for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        cin >> a >> b >> c;

        a--; b--;
        adj[a].push_back({ b, c });
        adj[b].push_back({ a, c });
    }

    vector<long long> min_u = min_dist(adj, u, n);
    vector<long long> min_v = min_dist(adj, v, n);

    vector<long long> ans_u(n, -1);
    vector<long long> ans_v(n, -1);
    vector<long long> ans(n, -1);
    vector<long long> cost(n, -1);

    priority_queue<Path, vector<Path>, greater<Path>> q;
    q.push({ s, 0, min_u[s], min_v[s] });

    while (!q.empty()) {
        auto [ r, c, u_dist, v_dist ] = q.top();
        q.pop();

        if (ans[r] == -1) {
            cost[r] = c;
            ans[r] = u_dist + v_dist;
        }

        if (cost[r] < c) continue;
        if (ans[r] < u_dist + v_dist) continue;

        for (auto [ p, w ] : adj[r]) {
            q.push({ p, c + w, min(u_dist, min_u[p]), min(v_dist, min_v[p]) });
        }
    }

    cout << ans[t];

    return 0;
}

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