Submission #335622

#	Time	Username	Problem	Language	Result	Execution time	Memory
335622		ryno	Commuter Pass (JOI18_commuter_pass)	C++14	0 / 100	391 ms	17632 KiB

commuter_pass

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

ll N, M, S, T, U, V, dist[5][100005];
bool good[100005];
pair<ll, ll> best[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<int>::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 });
            }
        }
    }
}

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

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

    ll output = dist[1][S] + dist[2][S];
    dist[3][S] = dist[1][S];
    pq.push({ 0, 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]) {
                int newD = min(dist[1][child.second], dist[3][curr.second]);
                if (newD < dist[3][child.second]) {
                    output = min(output, newD + dist[2][child.second]);
                    dist[3][child.second] = newD;
                    pq.push({ newD, child.second });
                }
            }
        }
    }
    return output;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(0);
    cin >> N >> M >> S >> T >> U >> V;

    ll a, b, c;
    for (ll 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 (1 then 2 or 2 then 1)
    dk(U, 1);
    dk(V, 2);
    dk(T, 0);
    ll ans = solve();
    swap(S, T);
    dk(T, 0);
    cout << min(ans, solve());
}

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