제출 #1188281

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

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

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

struct Edge {
    int to;
    ll cost;
    int id;
};

vector<vector<Edge>> adj;
vector<tuple<int, int, ll>> edges;

// Dijkstra: returns shortest distance from src and previous node tracking
vector<ll> dijkstra(int src, vector<vector<Edge>>& graph) {
    vector<ll> dist(N + 1, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;

    dist[src] = 0;
    pq.emplace(0, src);

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

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

    return dist;
}

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

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

    adj.resize(N + 1);

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

    // First Dijkstra from S and from T
    vector<ll> distS = dijkstra(S, adj);
    vector<ll> distT = dijkstra(T, adj);

    ll minPathST = distS[T];

    // Build new graph with some edges 0-cost if they are on some shortest S→T path
    vector<vector<Edge>> modified(N + 1);

    for (int i = 0; i < M; ++i) {
        auto [a, b, c] = edges[i];

        bool inShortestPath = false;
        if (distS[a] + c + distT[b] == minPathST ||
            distS[b] + c + distT[a] == minPathST) {
            inShortestPath = true;
        }

        if (inShortestPath) {
            modified[a].push_back({b, 0, i});
            modified[b].push_back({a, 0, i});
        } else {
            modified[a].push_back({b, c, i});
            modified[b].push_back({a, c, i});
        }
    }

    // Dijkstra on modified graph from U to V
    vector<ll> distUV = dijkstra(U, modified);
    cout << distUV[V] << "\n";

    return 0;
}

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