Submission #1277738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277738		ssseul	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	285 ms	22436 KiB

commuter_pass

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

typedef long long ll;
const ll INF = LLONG_MAX / 4;

vector<pair<ll, ll>> graph[100001];
ll du[100001], dv[100001], ds[100001], dp[2][100001], ans;
bool visited[100001];

// Dijkstra chuẩn với min-heap
void dijkstra1(ll start, ll arr[]) {
    fill(arr, arr + 100001, INF);
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    pq.push({0, start});
    arr[start] = 0;

    while (!pq.empty()) {
        auto [cost, node] = pq.top(); pq.pop();
        if (cost > arr[node]) continue;
        for (auto &i : graph[node]) {
            ll nxt = i.first, w = i.second;
            if (arr[nxt] > cost + w) {
                arr[nxt] = cost + w;
                pq.push({arr[nxt], nxt});
            }
        }
    }
}

// Dijkstra + DP trên DAG shortest-path từ start
void dijkstra2(ll start, ll end) {
    fill(ds, ds + 100001, INF);
    fill(dp[0], dp[0] + 100001, INF);
    fill(dp[1], dp[1] + 100001, INF);

    priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, greater<pair<ll, pair<ll, ll>>>> pq;
    pq.push({0, {start, 0}});
    ds[start] = 0;
    dp[0][start] = du[start];
    dp[1][start] = dv[start];

    while (!pq.empty()) {
        auto [cost, p] = pq.top(); pq.pop();
        auto [node, par] = p;

        if (cost > ds[node]) continue; // Không duyệt node đã tối ưu hơn

        // Cập nhật dp từ parent
        if (node != start) {
            dp[0][node] = min(du[node], dp[0][par]);
            dp[1][node] = min(dv[node], dp[1][par]);
        }

        for (auto &i : graph[node]) {
            ll nxt = i.first, w = i.second;
            if (ds[nxt] > cost + w) {
                ds[nxt] = cost + w;
                pq.push({ds[nxt], {nxt, node}});
            }
            else if (ds[nxt] == cost + w) {
                // Cùng khoảng cách -> update nếu dp tốt hơn
                ll new_dpU = min(du[nxt], dp[0][node]);
                ll new_dpV = min(dv[nxt], dp[1][node]);
                if (new_dpU + new_dpV < dp[0][nxt] + dp[1][nxt]) {
                    dp[0][nxt] = new_dpU;
                    dp[1][nxt] = new_dpV;
                    pq.push({ds[nxt], {nxt, node}});
                }
            }
        }
    }

    ans = min(ans, dp[0][end] + dp[1][end]);
}

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

    ll n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;

    for (ll i = 0; i <= n; i++) graph[i].clear();

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

    dijkstra1(u, du);
    dijkstra1(v, dv);

    ans = du[v]; // Trường hợp không xài commuter pass

    dijkstra2(s, t);
    dijkstra2(t, s); // Đảo chiều đi lại

    cout << ans << '\n';
    return 0;
}

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