| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1211170 | Madhav_1608 | Commuter Pass (JOI18_commuter_pass) | C++20 | 0 ms | 0 KiB |
#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 // This might be an issue if you're dealing with very precise floating points, but seems ok for typical pathfinding where weights are integers/long longs.
#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()
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
// DFS to find all edges on *any* shortest path from s to t
// This function populates special_edges_adj and special_edges_rev_adj
void build_shortest_path_edges(ll current_node, ll target_s_end, const vector<vector<pll>>& adj_original) {
if (current_node == target_s_end) {
return; // Reached the target
}
if (dfs_visited[current_node]) {
return; // Avoid cycles or redundant processing
}
dfs_visited[current_node] = true;
for (const pll& neighbor_pair : adj_original[current_node]) {
ll neighbor = neighbor_pair.F;
ll weight = neighbor_pair.S;
// If the path from s_start to current_node + edge_weight + path from neighbor to t_end
// equals the shortest path from s_start to t_end, then this edge is on a shortest path.
// We need dist from t_end for this. Let's assume we also computed dist from t_end.
// To precisely replicate your logic, we'd need to trace predecessors.
// The original code's `prev` logic implicitly identified these by only considering direct predecessors on shortest paths.
// My previous detailed response's check: dist_s[u] + w + dist_t[v] == dist_s[t_end] is more robust for finding ALL such edges.
// To exactly mimic your prev logic, we iterate over neighbours, and if they
// satisfy dist[current_node] + weight == dist[neighbor]
// then neighbor is a predecessor of current_node on a shortest path.
// Your code builds `prev[p.F].push_back(c.S)` if alt == dist[p.F].
// This means `prev[neighbor]` would contain `current_node`.
// So, we are going *backwards* from t to s.
// The original code uses a queue to traverse the `prev` graph, which essentially does a BFS on the reverse of the shortest path DAG.
// We can do this explicitly or with a direct BFS.
// Replicating the prev-based approach:
// We need `dist_s` (shortest distances from `s_start`) computed in `solve`.
if (dist_s_global[current_node] != MAXN &&
dist_s_global[neighbor] != MAXN &&
dist_s_global[neighbor] + weight == dist_s_global[current_node]) { // current_node is a predecessor of neighbor
// on a shortest path from s.
// So, we're building the adj1 (t->s) from current_node to neighbor.
special_edges_adj[current_node].push_back({neighbor, 0});
special_edges_rev_adj[neighbor].push_back({current_node, 0}); // Corresponds to adj2
if (!dfs_visited[neighbor]) { // Recurse only if not yet visited
build_shortest_path_edges(neighbor, target_s_end, adj_original);
}
}
}
dfs_visited[current_node] = false; // Backtrack
}
ll func(vector<vector<pll>> &adj_original, vector<vector<pll>> &additional_adj, ll n, ll u_query, ll v_query){
// This func combines original graph edges and 'additional_adj' edges
// No need to copy 'adj_original' into a temporary 'adj' inside this function
// Use the combined logic directly.
vll dist(n,MAXN);
vector<bool> visited(n,false); // A fresh visited array for each Dijkstra call
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;
// Iterate through original graph edges
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});
}
}
// Iterate through additional (special) edges
for(pll &p : additional_adj[current_u]){
ll alt = current_d + p.S; // p.S will be 0 for these special edges
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++; // Adjust for 1-indexed nodes if present
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); // The base graph
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});
}
// Step 1: Run Dijkstra from s_start on the original graph
dist_s_global.assign(n, MAXN); // Initialize globally accessible dist_s
vector<bool> visited_dijkstra(n, false); // For the first Dijkstra run
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});
}
// No need to store `prev` here directly for memory optimization.
// We'll reconstruct using dist_s_global.
}
}
// Step 2: Build `adj1` and `adj2` (special_edges_adj and special_edges_rev_adj)
// This part replaces your original `prev` vector and subsequent queue processing.
// We'll use a DFS (or BFS) starting from `t_end` traversing backwards along shortest paths.
special_edges_adj.assign(n, vector<pll>()); // adj1
special_edges_rev_adj.assign(n, vector<pll>()); // adj2 (for the reverse direction)
dfs_visited.assign(n, false); // Reset visited for the DFS traversal
// Use a queue to simulate your original BFS-like traversal of `prev` graph
queue<ll> q_sp;
q_sp.push(t_end);
vector<bool> sp_visited_q(n, false); // To prevent adding nodes multiple times to queue
sp_visited_q[t_end] = true;
while(!q_sp.empty()){
ll current = q_sp.front();
q_sp.pop();
// Iterate through all neighbors in the original graph
// If a neighbor 'i' is a predecessor of 'current' on an s-t shortest path
for(const pll& edge : adj_original[current]){
ll neighbor = edge.F;
ll weight = edge.S;
// Condition for `neighbor` being a predecessor of `current` on a shortest path from `s_start`:
// dist_s[neighbor] + weight == dist_s[current]
if (dist_s_global[neighbor] != MAXN && dist_s_global[current] != MAXN &&
dist_s_global[neighbor] + weight == dist_s_global[current]) {
// This edge (neighbor -> current) is on a shortest path.
// It means `current` has `neighbor` as a predecessor.
// Your original `adj1[c].push_back({i,0})` corresponds to `adj1[current].push_back({neighbor,0})`
special_edges_adj[current].push_back({neighbor, 0});
// Your original `adj2[j.F].push_back({i,0})` corresponds to `adj2[neighbor].push_back({current,0})`
special_edges_rev_adj[neighbor].push_back({current, 0});
if (!sp_visited_q[neighbor]) {
sp_visited_q[neighbor] = true;
q_sp.push(neighbor);
}
}
}
}
// Step 3: Call func for both scenarios (adj1 and adj2)
// func(adj, adj1, n, u, v) --> func(adj_original, special_edges_adj, n, u_query, v_query)
// func(adj, adj2, n, u, v) --> func(adj_original, special_edges_rev_adj, n, u_query, v_query)
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);
// init_code(); // This line is commented out, so it won't affect behavior
ll t=1;
// cin >> t; // Only one test case as per comments
while(t--){
solve();
}
return 0;
}