Submission #335619

#	Time	Username	Problem	Language	Result	Execution time	Memory
335619		ryno	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	2077 ms	262148 KiB

commuter_pass

#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <queue>
using namespace std;

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

void dk(int s, int id) {
    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 });
            }
        }
    }
}

pair<int, int> updated(int node, pair<int, int> newVal) {
    return { min(best[node].first, newVal.first), min(best[node].second, newVal.second) };
}

int solve() {
    int output = numeric_limits<int>::max();
    dist[3][S] = dist[1][S];
    pq.push({ 0, S });
    while (!pq.empty()) {
        auto curr = pq.top();
        pq.pop();

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

int main() {
    fill(dist[0], dist[4], numeric_limits<int>::max());
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> N >> M >> S >> T >> U >> V;

    int a, b, c;
    for (int i = 0; i < M; ++i) {
        cin >> a >> b >> c;
        routes[a].push_back({ c, b });
        routes[b].push_back({ c, a });
    }

    // dist[0] = nuke path
    // dist[1] = distances to U
    // dist[2] = distances to V
    // dist[3] = u_x to u + v_x to v (considering dist[1] then dist[2])
    dk(T, 0);
    dk(U, 1);
    dk(V, 2);
    cout << solve();
}

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