Submission #1224783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224783		nanaseyuzuki	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	220 ms	49616 KiB

commuter_pass

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

#define int long long
#define pii pair<int, int>
const int N = 2e5 + 5, INF = 4e18;

int n, m;
vector<pii> adj[N];
set<int> special[N]; // special[u] contains v if u->v is on the shortest path from A to B

int dA[N], dB[N];

void dijkstra(int src, int d[]) {
    fill(d + 1, d + n + 1, INF);
    d[src] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du > d[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int A, B, C, D;
    cin >> n >> m >> A >> B >> C >> D;

    vector<tuple<int,int,int>> edges;
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
        edges.emplace_back(u, v, w);
    }

    // Find shortest paths from A and B
    dijkstra(A, dA);
    dijkstra(B, dB);
    int shortest = dA[B];

    // Mark all edges on any shortest path from A -> B
    for (auto [u, v, w] : edges) {
        if (dA[u] + w + dB[v] == shortest)
            special[u].insert(v);
        if (dA[v] + w + dB[u] == shortest)
            special[v].insert(u);
    }

    // dp[u][entered][exited]
    int dp[N][2][2];
    for (int i = 1; i <= n; ++i)
        for (int e = 0; e < 2; ++e)
            for (int x = 0; x < 2; ++x)
                dp[i][e][x] = INF;

    dp[C][0][0] = 0;
    using State = tuple<int, int, int, int>; // (cost, u, entered, exited)
    priority_queue<State, vector<State>, greater<State>> pq;
    pq.push({0, C, 0, 0});

    while (!pq.empty()) {
        auto [cost, u, entered, exited] = pq.top(); pq.pop();
        if (cost > dp[u][entered][exited]) continue;

        for (auto [v, w] : adj[u]) {
            if (entered == 0 && exited == 0) {
                // enter special path
                if (special[u].count(v)) {
                    if (dp[v][1][0] > cost) {
                        dp[v][1][0] = cost;
                        pq.push({cost, v, 1, 0});
                    }
                }
                // go normally
                if (dp[v][0][0] > cost + w) {
                    dp[v][0][0] = cost + w;
                    pq.push({cost + w, v, 0, 0});
                }
            } else if (entered == 1 && exited == 0) {
                // continue on special path (free)
                if (special[u].count(v)) {
                    if (dp[v][1][0] > cost) {
                        dp[v][1][0] = cost;
                        pq.push({cost, v, 1, 0});
                    }
                } else {
                    // leave special path
                    if (dp[v][1][1] > cost + w) {
                        dp[v][1][1] = cost + w;
                        pq.push({cost + w, v, 1, 1});
                    }
                }
            } else if (entered == 1 && exited == 1) {
                // must pay
                if (dp[v][1][1] > cost + w) {
                    dp[v][1][1] = cost + w;
                    pq.push({cost + w, v, 1, 1});
                }
            }
        }
    }

    int res = min({dp[D][0][0], dp[D][1][0], dp[D][1][1]});
    cout << (res >= INF ? -1 : res) << "\n";
}

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