Submission #1230619

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230619		Jovica	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	144 ms	21344 KiB

commuter_pass

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

static const int MAXN = 100000 + 5;
vector<pair<int,ll>> adj[MAXN];
ll odS[MAXN];
bool visited[MAXN], onSP[MAXN];

void dijkstra_from_T(int T) {
    fill(odS, odS+MAXN, LLONG_MAX);
    memset(visited, 0, sizeof(visited));
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    odS[T] = 0;
    pq.push({0, T});

    while (!pq.empty()) {
        auto [d, v] = pq.top(); pq.pop();
        if (visited[v]) continue;
        visited[v] = true;

        for (auto [u, w] : adj[v]) {
            if (odS[u] > d + w) {
                odS[u] = d + w;
                pq.push({odS[u], u});
            }
        }
    }
}

void dfs_mark_SP(int v, int T) {
    // we assume onSP[v] is already set true by the caller
    if (v == T) return;
    for (auto [u, w] : adj[v]) {
        if (!onSP[u] && odS[v] - w == odS[u]) {
            onSP[u] = true;
            dfs_mark_SP(u, T);
        }
    }
}

ll minMoney(int start, int goal) {
    memset(visited, 0, sizeof(visited));
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [cost, v] = pq.top(); pq.pop();
        if (visited[v]) continue;
        visited[v] = true;
        if (v == goal) return cost;

        for (auto [u, w] : adj[v]) {
            ll extra = (onSP[v] && onSP[u]) ? 0 : w;
            pq.push({cost + extra, u});
        }
    }
    return -1; // unreachable
}

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

    int n, m, S, T, pocetok, kraj;
    cin >> n >> m >> S >> T >> pocetok >> kraj;
    for (int i = 1; i <= n; i++) {
        adj[i].clear();
        onSP[i] = false;
    }

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

    // 1) get distances *to* T
    dijkstra_from_T(T);

    // 2) mark all nodes on *some* S→T shortest path
    onSP[S] = true;
    dfs_mark_SP(S, T);

    // 3) find min “extra‐money” from pocetok to kraj
    cout << minMoney(pocetok, kraj) << "\n";
    return 0;
}

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