Submission #1211171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211171		Madhav_1608	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	190 ms	27820 KiB

commuter_pass

#include <iostream>
#include <stack>
#include <queue>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <iomanip>
#include <cstring>
#include <stdio.h>
#include <assert.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<long long> vll;
typedef pair<ll,ll> pll;

#define double long double
#define F first
#define S second
const double eps = 1e-9;
#define FOR(i,a,b) for(long long i=a;i<b;i++)
#define all(v) v.begin(),v.end()

// Define MAXN here, globally accessible
const ll MAXN = 1e17; // A sufficiently large value for infinity

template <typename I>
void print(vector<I> &v){
    FOR(i,0,v.size()){cout << v[i] << " ";}
    cout << "\n";
}

ll gcd(ll a,ll b){
    if(a==0){return b;}
    else if(b==0){return a;}
    else if(a<b){return gcd(b%a,a);}
    else{return gcd(a%b,b);}
}

ll lcm(ll a,ll b){
    return (a/gcd(a,b))*b;
}

// Global variable or passed by reference to avoid recreating
// Used to store edges on *any* shortest path from s to t
vector<vector<pll>> special_edges_adj;
vector<vector<pll>> special_edges_rev_adj; // For the "adj2" equivalent

// Visited array for DFS to prevent cycles in the shortest path reconstruction
vector<bool> dfs_visited;
vll dist_s_global; // Store dist from s globally or pass around

// build_shortest_path_edges function (removed as it was causing confusion with prev logic,
// and the BFS queue approach directly builds special_edges_adj)
/*
void build_shortest_path_edges(ll current_node, ll target_s_end, const vector<vector<pll>>& adj_original) {
    // ... (This function's logic was superseded by the BFS queue in solve)
}
*/

ll func(vector<vector<pll>> &adj_original, vector<vector<pll>> &additional_adj, ll n, ll u_query, ll v_query){
    vll dist(n,MAXN); // MAXN is now in scope
    vector<bool> visited(n,false);
    priority_queue<pll,vector<pll>,greater<pll>> pq;

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

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

        ll current_d = c.F;
        ll current_u = c.S;

        if(visited[current_u]) continue;
        visited[current_u] = true;

        for(pll &p : adj_original[current_u]){
            ll alt = current_d + p.S;
            if(alt < dist[p.F]){
                dist[p.F] = alt;
                pq.push({alt,p.F});
            }
        }

        for(pll &p : additional_adj[current_u]){
            ll alt = current_d + p.S;
            if(alt < dist[p.F]){
                dist[p.F] = alt;
                pq.push({alt,p.F});
            }
        }
    }
    return dist[v_query];
}

void solve(){
    ll n,m;
    cin >> n >> m;
    n++;
    ll s_start, t_end;
    cin >> s_start >> t_end;
    ll u_query, v_query;
    cin >> u_query >> v_query;

    vector<vector<pll>> adj_original(n);
    for(ll i=0; i<m; ++i){
        ll a,b,c;
        cin >> a >> b >> c;
        adj_original[a].push_back({b,c});
        adj_original[b].push_back({a,c});
    }

    dist_s_global.assign(n, MAXN); // MAXN is now in scope
    vector<bool> visited_dijkstra(n, false);
    priority_queue<pll,vector<pll>,greater<pll>> pq_s;

    pq_s.push({0,s_start});
    dist_s_global[s_start] = 0;

    while(!pq_s.empty()){
        pll c = pq_s.top();
        pq_s.pop();

        ll current_d = c.F;
        ll current_u = c.S;

        if(visited_dijkstra[current_u]) continue;
        visited_dijkstra[current_u] = true;

        for(pll &p : adj_original[current_u]){
            ll alt = current_d + p.S;
            if(alt < dist_s_global[p.F]){
                dist_s_global[p.F] = alt;
                pq_s.push({alt,p.F});
            }
        }
    }

    special_edges_adj.assign(n, vector<pll>());
    special_edges_rev_adj.assign(n, vector<pll>());
    // dfs_visited.assign(n, false); // No longer needed for DFS if using BFS queue for special edges

    queue<ll> q_sp;
    q_sp.push(t_end);
    vector<bool> sp_visited_q(n, false);
    sp_visited_q[t_end] = true;

    while(!q_sp.empty()){
        ll current = q_sp.front();
        q_sp.pop();

        for(const pll& edge : adj_original[current]){
            ll neighbor = edge.F;
            ll weight = edge.S;

            // This condition correctly identifies if 'neighbor' is a predecessor of 'current'
            // on a shortest path from 's_start'
            if (dist_s_global[neighbor] != MAXN && dist_s_global[current] != MAXN &&
                dist_s_global[neighbor] + weight == dist_s_global[current]) {

                special_edges_adj[current].push_back({neighbor, 0});
                special_edges_rev_adj[neighbor].push_back({current, 0});

                if (!sp_visited_q[neighbor]) {
                    sp_visited_q[neighbor] = true;
                    q_sp.push(neighbor);
                }
            }
        }
    }

    cout << min(func(adj_original, special_edges_adj, n, u_query, v_query),
                func(adj_original, special_edges_rev_adj, n, u_query, v_query)) << "\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t=1;
    while(t--){
        solve();
    }
    return 0;
}

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