Submission #701642

#	Time	Username	Problem	Language	Result	Execution time	Memory
701642		phi	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	554 ms	33572 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 {
    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;
    }

    friend bool operator<(const Path &l, const Path &r) {
        return r > l;
    }
};

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<Path> ans(n);
    vector<bool> visited(n);

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

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

        if (!visited[r]) {
            visited[r] = true;
            ans[r] = path;
        } else {
            continue;
        }

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

    cout << min((ans[t].u_dist + ans[t].v_dist), min_u[v]);

    return 0;
}

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