Submission #701616

#	Time	Username	Problem	Language	Result	Execution time	Memory
701616		phi	Commuter Pass (JOI18_commuter_pass)	C++17	16 / 100	628 ms	32060 KiB

commuter_pass

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

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(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) continue;
        ans[r] = u_dist + v_dist;

        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: 16 / 16
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 45