Submission #1211167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211167		Madhav_1608	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	198 ms	32084 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

// Use long long for distances to prevent overflow
typedef long long ll;
typedef std::pair<ll, ll> pll; // {distance, node}

const ll MAXN = 1e17; // A sufficiently large value for infinity

// Function to run Dijkstra from a source node
std::vector<ll> dijkstra(ll n, const std::vector<std::vector<pll>>& adj, ll source) {
    std::vector<ll> dist(n, MAXN);
    std::priority_queue<pll, std::vector<pll>, std::greater<pll>> pq;

    dist[source] = 0;
    pq.push({0, source});

    while (!pq.empty()) {
        pll current = pq.top();
        pq.pop();

        ll d = current.first;
        ll u = current.second;

        if (d > dist[u]) {
            continue; // Already found a shorter path
        }

        for (const pll& edge : adj[u]) {
            ll v = edge.first;
            ll weight = edge.second;

            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

void solve() {
    ll n, m;
    std::cin >> n >> m;
    n++; // Nodes are 1-indexed, so adjust size

    ll s_start, t_end;
    std::cin >> s_start >> t_end;

    ll u_query, v_query;
    std::cin >> u_query >> v_query;

    std::vector<std::vector<pll>> adj(n);
    std::vector<std::vector<pll>> rev_adj(n); // For Dijkstra from t_end (or finding dist_t)

    for (ll i = 0; i < m; ++i) {
        ll a, b, c;
        std::cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
        rev_adj[b].push_back({a, c}); // Build reverse graph for dist from t_end
        rev_adj[a].push_back({b, c});
    }

    // Run Dijkstra from s_start to get shortest path distances
    std::vector<ll> dist_s = dijkstra(n, adj, s_start);

    // Run Dijkstra from t_end on the original graph to get distances from t_end
    // (This is equivalent to running Dijkstra from t_end on the reverse graph)
    std::vector<ll> dist_t = dijkstra(n, adj, t_end);

    // Now, run Dijkstra from u_query to v_query
    // The "special" edges are those on a shortest path from s_start to t_end.
    // An edge (x, y) with weight w is on a shortest path from s_start to t_end
    // if dist_s[x] + w + dist_t[y] == dist_s[t_end] (or dist_s[y] + w + dist_t[x] == dist_s[t_end])
    // The problem implies we add edges in both directions for shortest paths.
    
    std::vector<ll> final_dist(n, MAXN);
    std::priority_queue<pll, std::vector<pll>, std::greater<pll>> pq_final;

    final_dist[u_query] = 0;
    pq_final.push({0, u_query});

    ll min_path_length = MAXN;

    while (!pq_final.empty()) {
        pll current = pq_final.top();
        pq_final.pop();

        ll d = current.first;
        ll u = current.second;

        if (d > final_dist[u]) {
            continue;
        }

        // Check if we reached the target node
        if (u == v_query) {
            min_path_length = std::min(min_path_length, final_dist[u]);
            continue; // Can potentially stop early if looking for just one shortest path
        }

        // Iterate over all neighbors
        for (const pll& edge : adj[u]) {
            ll v = edge.first;
            ll weight = edge.second;

            // Option 1: Traverse original edge
            ll alt1 = final_dist[u] + weight;
            if (alt1 < final_dist[v]) {
                final_dist[v] = alt1;
                pq_final.push({alt1, v});
            }
            
            // Option 2: Traverse 'special' edges (part of s-t shortest path)
            // This is where the core logic of the problem comes in.
            // If the original edge (u, v) with weight 'weight' is part of an s-t shortest path.
            // We consider adding this edge with 0 cost in both directions.
            // This means if (u,v) is part of a shortest path from s to t,
            // we can go u->v (cost 0) or v->u (cost 0).
            // A more accurate interpretation for "less memory code" would be
            // to only add these edges on the fly if they are beneficial.
            
            // If (u,v) is on a shortest path from s_start to t_end
            if (dist_s[u] != MAXN && dist_t[v] != MAXN && dist_s[u] + weight + dist_t[v] == dist_s[t_end]) {
                // This edge (u,v) is on a shortest path. Consider 0 cost.
                ll alt_special_fwd = final_dist[u] + 0; // Forward on special path
                if (alt_special_fwd < final_dist[v]) {
                    final_dist[v] = alt_special_fwd;
                    pq_final.push({alt_special_fwd, v});
                }
            }

            // If (v,u) is on a shortest path from s_start to t_end (i.e., u is 'prev' of v on SP)
            // This covers the reverse direction without needing a reverse graph specifically for this check.
            if (dist_s[v] != MAXN && dist_t[u] != MAXN && dist_s[v] + weight + dist_t[u] == dist_s[t_end]) {
                // This edge (v,u) is on a shortest path. Consider 0 cost.
                ll alt_special_bwd = final_dist[u] + 0; // Backward on special path
                if (alt_special_bwd < final_dist[v]) {
                    final_dist[v] = alt_special_bwd;
                    pq_final.push({alt_special_bwd, v});
                }
            }
        }
    }
    std::cout << final_dist[v_query] << "\n";
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
    solve();
    return 0;
}

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