Submission #335639

#	Time	Username	Problem	Language	Result	Execution time	Memory
335639		ryno	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	727 ms	20084 KiB

commuter_pass

#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <queue>
#include <random>
#include <time.h>
using namespace std;
typedef long long ll;

ll N, M, S, T, U, V, dist[5][100005];
vector<pair<ll, ll>> routes[100005];
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;

void dk(ll s, ll id) {
    fill(begin(dist[id]), end(dist[id]), numeric_limits<ll>::max());

    dist[id][s] = 0;
    pq.push({ 0, s });
    while (!pq.empty()) {
        auto curr = pq.top();
        pq.pop();
        if (curr.first > dist[id][curr.second]) continue;

        for (auto child : routes[curr.second]) {
            if (child.first + curr.first < dist[id][child.second]) {
                dist[id][child.second] = child.first + curr.first;
                pq.push({ dist[id][child.second], child.second });
            }
        }
    }
}

ll solve(ll first, ll second) {
    fill(begin(dist[3]), end(dist[3]), numeric_limits<ll>::max());

    ll output = dist[first][S] + dist[second][S];
    dist[3][S] = dist[first][S];
    pq.push({ dist[3][S], S });
    while (!pq.empty()) {
        auto curr = pq.top();
        pq.pop();
        if (curr.first > dist[3][curr.second]) continue;

        for (auto child : routes[curr.second]) {
            if (dist[0][child.second] + child.first == dist[0][curr.second]) {
                ll newD = min(dist[first][child.second], dist[3][curr.second]);
                if (newD < dist[3][child.second]) {
                    output = min(output, newD + dist[second][child.second]);
                    dist[3][child.second] = newD;
                    pq.push({ newD, child.second });
                }
            }
        }
    }
    return output;
}

ll genRand() {
    return rand() % N + 1;
}

int main() {
    srand(time(NULL));
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> N >> M >> S >> T >> U >> V;
    if (T == U || T == V) swap(S, T);

    for (ll i = 0, a, b, c; i < M; ++i) {
        cin >> a >> b >> c;
        routes[a].push_back({ c, b });
        routes[b].push_back({ c, a });
    }
    for (ll rep = 0; rep < 1; ++rep) {
        //S = genRand(), T = genRand(), U = genRand(), V = genRand();
        dk(T, 0); // dist[0] = nuke path
        dk(U, 1); // dist[1] = distances to U
        dk(V, 2); // dist[2] = distances to V
        // dist[3] = u_x to u + v_x to v (1 then 2 or 2 then 1)
        //cout << S << T << " " << U << V << " ";
        cout << min({ solve(1, 2), solve(2, 1), dist[1][V] }) << "\n";
    }
}

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