Submission #1203538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203538		merciless_lassie	Commuter Pass (JOI18_commuter_pass)	C++20	15 / 100	273 ms	22008 KiB

commuter_pass

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

typedef long long ll;
constexpr ll INF = LLONG_MAX / 2;  // Safe large value to avoid overflow
constexpr int MAXN = 100001;

vector<pair<ll, ll>> graph[MAXN];  // graph[u] = list of (neighbor, cost)
ll distU[MAXN], distV[MAXN], distS[MAXN];  // Shortest distances from U, V, and S
ll dp[2][MAXN];  // dp[0][i] = min distU on path to i, dp[1][i] = min distV
bool visited[MAXN];
ll answer;  // Final answer: minimum cost from U to V

// Regular Dijkstra to compute shortest distances from one source
void dijkstra(ll start, ll dist[]) {
    fill(dist, dist + MAXN, INF);
    fill(visited, visited + MAXN, false);

    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<>> pq;
    pq.push({0, start});
    dist[start] = 0;

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

        for (auto [neighbor, edgeCost] : graph[node]) {
            if (dist[neighbor] > dist[node] + edgeCost) {
                dist[neighbor] = dist[node] + edgeCost;
                pq.push({dist[neighbor], neighbor});
            }
        }
    }
}

// Modified Dijkstra to traverse a shortest path tree from S to T
// For each node on shortest S→T path, track min distU and distV
void dijkstraOnShortestPathTree(ll source, ll target) {
    fill(distS, distS + MAXN, INF);
    fill(dp[0], dp[0] + MAXN, INF);
    fill(dp[1], dp[1] + MAXN, INF);
    fill(visited, visited + MAXN, false);

    priority_queue<tuple<ll, ll, ll>, vector<tuple<ll, ll, ll>>, greater<>> pq;
    pq.push({0, source, -1});  // (cost, currentNode, parentNode)
    distS[source] = 0;

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

        // Update dp for current node based on its parent
        if (parent != -1) {
            dp[0][node] = min(distU[node], dp[0][parent]);
            dp[1][node] = min(distV[node], dp[1][parent]);
        } else {
            dp[0][node] = distU[node];
            dp[1][node] = distV[node];
        }

        for (auto [neighbor, edgeCost] : graph[node]) {
            if (distS[neighbor] > distS[node] + edgeCost) {
                distS[neighbor] = distS[node] + edgeCost;
                pq.push({distS[neighbor], neighbor, node});
            }
        }
    }

    // If this S-T path has total cost equal to shortest S-T path
    // Then consider its use to minimize U-V cost
    answer = min(answer, dp[0][target] + dp[1][target]);
}

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

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

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

    // Compute shortest paths from U, V, and S
    dijkstra(u, distU);
    dijkstra(v, distV);

    // Initialize answer with the full cost U→V without any commuter pass
    answer = distU[v];

    // Evaluate both S→T and T→S as possible commuter pass paths
    dijkstraOnShortestPathTree(s, t);
    dijkstraOnShortestPathTree(t, s);

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

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