Submission #1233810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233810		orzorzorz	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	263 ms	21072 KiB

commuter_pass

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

    #define pii pair<long long, int>
    #define ll long long
    const ll INF = 1e18;
    const int MAXN = 1e5 + 5;

    int N, M;
    int S, T, U, V;
    vector<tuple<int, int, int>> edges;
    vector<pii> G[MAXN];
    ll distS[MAXN], distT[MAXN], distU[MAXN];

    // Dijkstra 從 start 開始
    void dijkstra(int start, ll dist[]) {
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        fill(dist, dist + N + 1, INF);
        dist[start] = 0;
        pq.push({0, start});

        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dist[u]) continue;
            for (auto [v, w] : G[u]) {
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
    }

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

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

        // 儲存邊，同時建立圖
        for (int i = 0; i < M; ++i) {
            int a, b, c;
            cin >> a >> b >> c;
            edges.emplace_back(a, b, c);
            G[a].emplace_back(b, c);
            G[b].emplace_back(a, c);
        }

        // 跑 Dijkstra 求 S -> all, T -> all
        dijkstra(S, distS);
        dijkstra(T, distT);

        ll distST = distS[T];

        // 清空圖準備重建
        for (int i = 1; i <= N; ++i) G[i].clear();

        // 找在 ST 最短路上的邊，設為 0，其他照原本
        for (auto &[a, b, c] : edges) {
            if (distS[a] + c + distT[b] == distST || distS[b] + c + distT[a] == distST) {
                G[a].emplace_back(b, 0);
                G[b].emplace_back(a, 0);
            } else {
                G[a].emplace_back(b, c);
                G[b].emplace_back(a, c);
            }
        }

        // 從 U 跑 Dijkstra 求最短距離到 V
        dijkstra(U, distU);

        // 輸出答案
        if (distU[V] == INF) cout << -1 << '\n';
        else cout << distU[V] << '\n';

        return 0;
    }

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