Submission #1265169

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265169		andyo	Commuter Pass (JOI18_commuter_pass)	C++20	16 / 100	240 ms	19324 KiB

commuter_pass

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

using namespace std;

const long long INF = 1e18;

struct Edge {
    int to;
    long long cost;
};

vector<long long> dijkstra(int start, const vector<vector<Edge>>& graph) {
    int n = graph.size();
    vector<long long> dist(n, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (const Edge& e : graph[u]) {
            if (dist[u] + e.cost < dist[e.to]) {
                dist[e.to] = dist[u] + e.cost;
                pq.push({dist[e.to], e.to});
            }
        }
    }
    
    return dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    cin >> N >> M;
    
    int S, T, U, V;
    cin >> S >> T >> U >> V;
    S--; T--; U--; V--;  // Convert to 0-indexed
    
    vector<vector<Edge>> graph(N);
    
    for (int i = 0; i < M; i++) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        a--; b--;  // Convert to 0-indexed
        
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    
    // Calculate shortest distances from all key points
    vector<long long> distS = dijkstra(S, graph);
    vector<long long> distT = dijkstra(T, graph);
    vector<long long> distU = dijkstra(U, graph);
    vector<long long> distV = dijkstra(V, graph);
    
    long long shortestST = distS[T];
    
    // Initialize result with direct path from U to V (no commuter pass used)
    long long result = distU[V];
    
    // The key insight: The commuter pass covers some shortest path from S to T.
    // We can use this path for free in our journey from U to V.
    // We need to consider all possible ways to utilize this free path:
    
    // Strategy 1: Go U -> S -> T -> V (use entire S->T path)
    result = min(result, distU[S] + distT[V]);
    
    // Strategy 2: Go U -> T -> S -> V (use entire T->S path)
    result = min(result, distU[T] + distS[V]);
    
    // Strategy 3: Use intermediate points on the shortest S->T path
    // For any point X that lies on some shortest path from S to T:
    // - Distance from S to X plus distance from X to T equals shortestST
    // - We can go U -> X -> V, using either S->X or X->T portion for free
    
    for (int x = 0; x < N; x++) {
        // Check if x lies on some shortest path from S to T
        if (distS[x] + distT[x] == shortestST) {
            // Case 3a: U -> X -> V, utilizing the fact that we can reach X from S for free
            // or reach T from X for free (whichever is better)
            result = min(result, distU[x] + distV[x]);
            
            // Case 3b: U -> S -> X -> V (S->X is free)
            result = min(result, distU[S] + distV[x]);
            
            // Case 3c: U -> X -> T -> V (X->T is free)  
            result = min(result, distU[x] + distV[T]);
        }
    }
    
    cout << result << endl;
    
    return 0;
}

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