제출 #1250982

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1250982		duyen	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	2093 ms	36776 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;

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);
    }

    // Precompute distances
    auto distS = dijkstra(S, graph);
    auto distT = dijkstra(T, graph);
    auto distU = dijkstra(U, graph);

    int totalST = distS[T];
    int answer = INF;

    for (auto &[a, b, c] : edges) {
        bool onShortestPath = false;
        if (distS[a] + c + distT[b] == totalST) onShortestPath = true;
        if (distS[b] + c + distT[a] == totalST) onShortestPath = true;

        if (!onShortestPath) continue;

        // Build new graph with only (a,b) free
        vector<vector<pair<int, int>>> newGraph(N + 1);
        for (auto &[x, y, w] : edges) {
            int cost = w;
            if ((x == a && y == b) || (x == b && y == a)) {
                cost = 0; // this edge is free
            }
            newGraph[x].emplace_back(y, cost);
            newGraph[y].emplace_back(x, cost);
        }

        auto dist = dijkstra(U, newGraph);
        answer = min(answer, dist[V]);
    }

    cout << answer << "\n";
}

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