Submission #1166373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166373		merciless_lassie	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	336 ms	49440 KiB

commuter_pass

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int N = 1e6 + 5;
#define II pair<int,int>
#define fi first
#define se second
int n, m;
int s, t, U, V;
int du[N], dv[N], ds[N];
int dp[2][N];
int ans;
bool visited[N];
vector<II> adj[N];

template<class X, class Y> bool mini(X& x, const Y y) {
    if (x > y) return x = y, 1;
    return 0;
}

// Standard Dijkstra to compute shortest paths from start to all other nodes
void dijkstra1(int start, int dist[]) {
    memset(visited, false, sizeof(visited));
    
    priority_queue<II, vector<II>, greater<II>> q;
    q.push({0, start});
    
    while (!q.empty()) {
        int cost = q.top().fi;
        int node = q.top().se;
        q.pop();
        
        if (!visited[node]) {
            dist[node] = cost;
            visited[node] = true;
            
            for (II edge : adj[node]) {
                int next_node = edge.se;
                int next_cost = edge.fi;
                q.push({cost + next_cost, next_node});
            }
        }
    }
}

// Modified Dijkstra to find optimal path considering commuter pass
void dijkstra2(int start, int end) {
    // Initialize dp arrays
    for (int i = 0; i <= n; i++) {
        dp[0][i] = LLONG_MAX / 2;
        dp[1][i] = LLONG_MAX / 2;
    }
    
    memset(visited, false, sizeof(visited));
    
    priority_queue<pair<int, II>, vector<pair<int, II>>, greater<pair<int, II>>> q;
    q.push({0, {start, 0}});
    
    dp[0][0] = dp[1][0] = LLONG_MAX / 2;
    
    while (!q.empty()) {
        int cost = q.top().fi;
        int node = q.top().se.fi;
        int parent = q.top().se.se;
        q.pop();
        
        if (!visited[node]) {
            visited[node] = true;
            ds[node] = cost;
            
            // Update dp values - minimum cost to reach U and V from current node
            dp[0][node] = min(du[node], dp[0][parent]);
            dp[1][node] = min(dv[node], dp[1][parent]);
            
            for (II edge : adj[node]) {
                int next_node = edge.se;
                int next_cost = edge.fi;
                q.push({cost + next_cost, {next_node, node}});
            }
        } 
        else if (cost == ds[node]) {
            // If we found another path with same cost, check if it's better for U-V
            int new_cost_u = min(du[node], dp[0][parent]);
            int new_cost_v = min(dv[node], dp[1][parent]);
            
            if (new_cost_u + new_cost_v <= dp[0][node] + dp[1][node]) {
                dp[0][node] = new_cost_u;
                dp[1][node] = new_cost_v;
            }
        }
    }
    
    // Update the answer with the cost at the end node
    ans = min(ans, dp[0][end] + dp[1][end]);
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("_ab.inp", "r")) {
        freopen("_ab.inp", "r", stdin);
        freopen("_ab.out", "w", stdout);
    }
    
    cin >> n >> m;
    cin >> s >> t >> U >> V;
    
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({c, b});
        adj[b].push_back({c, a});
    }
    
    // Find shortest paths from U and V to all other nodes
    dijkstra1(U, du);
    dijkstra1(V, dv);
    
    // Set initial answer to the direct distance from U to V
    ans = du[V];
    
    // Try both directions for the commuter pass
    dijkstra2(s, t);
    dijkstra2(t, s);
    
    cout << ans;
    
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen("_ab.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen("_ab.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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