Submission #1265174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265174		andyo	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	270 ms	33412 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long ll;
typedef pair<ll, int> pli;

const ll INF = 1e18;

int main() {
    int n, m;
    cin >> n >> m;
    
    int s, t;
    cin >> s >> t;
    
    int u, v;
    cin >> u >> v;
    
    // Adjacency list to store the graph
    vector<vector<pair<int, ll>>> graph(n + 1);
    
    // Store all railways
    vector<tuple<int, int, ll>> railways(m);
    
    for (int i = 0; i < m; i++) {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        
        // Store the railway
        railways[i] = {a, b, c};
        
        // Add edges to the graph
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    
    // Dijkstra's algorithm to find shortest path from a given source
    auto dijkstra = [&](int source, vector<ll>& dist) {
        dist.assign(n + 1, INF);
        priority_queue<pli, vector<pli>, greater<pli>> pq;
        
        dist[source] = 0;
        pq.push({0, source});
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            if (d > dist[u]) continue;
            
            for (auto& [v, w] : graph[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
    };
    
    // Find shortest path from S to T in the original graph
    vector<ll> dist_s_to_all;
    dijkstra(s, dist_s_to_all);
    ll original_cost_s_to_t = dist_s_to_all[t];
    
    // For each valid S-T path, check the cost from U to V
    ll min_cost_u_to_v = INF;
    
    // Brute force through all possible paths from S to T
    // In a real implementation, we would optimize this further
    
    // Approach: Try all possible edges that could be part of commuter pass
    // For each possible set, compute the min cost from U to V
    
    // For simplicity, let's try a clever approach:
    // 1. Create a new graph where railways in S-T path have cost 0
    // 2. Find shortest path from U to V in this new graph
    
    // Find the original shortest path from S to T
    vector<int> parent(n + 1, -1);
    vector<bool> is_on_st_path(m, false);
    
    // Re-run Dijkstra from S to T to get the path
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    pq.push({0, s});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (u == t) break;
        
        for (auto& [v, w] : graph[u]) {
            if (dist_s_to_all[u] + w == dist_s_to_all[v]) {
                parent[v] = u;
                pq.push({dist_s_to_all[v], v});
                break;
            }
        }
    }
    
    // Mark edges on S-T path
    int curr = t;
    while (curr != s && parent[curr] != -1) {
        int prev = parent[curr];
        for (int i = 0; i < m; i++) {
            auto [a, b, c] = railways[i];
            if ((a == prev && b == curr) || (a == curr && b == prev)) {
                is_on_st_path[i] = true;
                break;
            }
        }
        curr = prev;
    }
    
    // Create a modified graph for U to V path
    vector<vector<pair<int, ll>>> modified_graph(n + 1);
    for (int i = 0; i < m; i++) {
        auto [a, b, c] = railways[i];
        ll new_cost = is_on_st_path[i] ? 0 : c;
        modified_graph[a].push_back({b, new_cost});
        modified_graph[b].push_back({a, new_cost});
    }
    
    // Find shortest path from U to V in the modified graph
    vector<ll> dist_u_to_all(n + 1, INF);
    dist_u_to_all[u] = 0;
    
    priority_queue<pli, vector<pli>, greater<pli>> pq2;
    pq2.push({0, u});
    
    while (!pq2.empty()) {
        auto [d, node] = pq2.top();
        pq2.pop();
        
        if (d > dist_u_to_all[node]) continue;
        
        for (auto& [next, weight] : modified_graph[node]) {
            if (dist_u_to_all[node] + weight < dist_u_to_all[next]) {
                dist_u_to_all[next] = dist_u_to_all[node] + weight;
                pq2.push({dist_u_to_all[next], next});
            }
        }
    }
    
    cout << dist_u_to_all[v] << endl;
    
    return 0;
}

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