제출 #1250975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1250975		duyen	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	295 ms	36312 KiB

commuter_pass

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

#define int long long
const int INF = 1e18;

int N, M;
vector<tuple<int, int, int>> edges;
vector<vector<pair<int, int>>> graph; // adjacency list

vector<int> dijkstra(int start, const vector<vector<pair<int, int>>>& g) {
    vector<int> dist(N + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    dist[start] = 0;
    pq.emplace(0, start);

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;

        for (auto &[v, cost] : g[u]) {
            if (dist[v] > dist[u] + cost) {
                dist[v] = dist[u] + cost;
                pq.emplace(dist[v], v);
            }
        }
    }

    return dist;
}

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

    int S, T, U, V;
    cin >> N >> M;
    cin >> S >> T;
    cin >> U >> V;

    graph.resize(N + 1);
    edges.reserve(M);

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

    // Step 1: Run Dijkstra from S, T, and U
    auto distS = dijkstra(S, graph);
    auto distT = dijkstra(T, graph);
    auto distU = dijkstra(U, graph);

    int totalDistST = distS[T];

    // Step 2: Build new graph where commuter pass edges are free
    vector<vector<pair<int, int>>> newGraph(N + 1);
    for (auto &[a, b, c] : edges) {
        if (distS[a] + c + distT[b] == totalDistST ||
            distS[b] + c + distT[a] == totalDistST) {
            // Edge is part of some S-T shortest path
            newGraph[a].emplace_back(b, 0);
            newGraph[b].emplace_back(a, 0);
        } else {
            newGraph[a].emplace_back(b, c);
            newGraph[b].emplace_back(a, c);
        }
    }

    // Step 3: Dijkstra from U to V on new graph
    auto finalDist = dijkstra(U, newGraph);
    cout << finalDist[V] << "\n";
}

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