Submission #1203540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203540		merciless_lassie	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	272 ms	20300 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr ll INF = LLONG_MAX / 2;
constexpr int MAXN = 100001;

struct Edge {
    int to;
    ll cost;
};

vector<Edge> graph[MAXN];

ll distFromU[MAXN], distFromV[MAXN], distFromS[MAXN];
ll minUOnPath[MAXN], minVOnPath[MAXN];
bool visited[MAXN];
ll answer;

void dijkstra(int start, ll dist[]) {
    fill(dist, dist + MAXN, INF);
    fill(visited, visited + MAXN, false);

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    pq.emplace(0, start);
    dist[start] = 0;

    while (!pq.empty()) {
        auto [cost, node] = pq.top(); pq.pop();
        if (visited[node]) continue;
        visited[node] = true;

        for (const Edge& e : graph[node]) {
            if (dist[e.to] > dist[node] + e.cost) {
                dist[e.to] = dist[node] + e.cost;
                pq.emplace(dist[e.to], e.to);
            }
        }
    }
}

void evaluatePath(int source, int target) {
    fill(distFromS, distFromS + MAXN, INF);
    fill(minUOnPath, minUOnPath + MAXN, INF);
    fill(minVOnPath, minVOnPath + MAXN, INF);
    fill(visited, visited + MAXN, false);

    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
    pq.emplace(0, source, -1);  // (cost, node, parent)
    distFromS[source] = 0;

    while (!pq.empty()) {
        auto [cost, node, parent] = pq.top(); pq.pop();
        if (visited[node]) continue;
        visited[node] = true;

        if (parent != -1) {
            minUOnPath[node] = min(distFromU[node], minUOnPath[parent]);
            minVOnPath[node] = min(distFromV[node], minVOnPath[parent]);
        } else {
            minUOnPath[node] = distFromU[node];
            minVOnPath[node] = distFromV[node];
        }

        for (const Edge& e : graph[node]) {
            if (distFromS[e.to] > distFromS[node] + e.cost) {
                distFromS[e.to] = distFromS[node] + e.cost;
                pq.emplace(distFromS[e.to], e.to, node);
            }
        }
    }

    answer = min(answer, minUOnPath[target] + minVOnPath[target]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, S, T, U, V;
    cin >> n >> m >> S >> T >> U >> V;

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

    dijkstra(U, distFromU);
    dijkstra(V, distFromV);

    answer = distFromU[V]; // No free commuter pass

    // Try both directions for the commuter pass
    evaluatePath(S, T);
    evaluatePath(T, S);

    cout << answer << '\n';
}

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