Hi, I am currently attempting the problem “Commuter Pass” from the Shortest Path Section in Gold.
I thought of an alternative solution where you create a 4-layered graph, the first representing that the commuter pass has not been used; the second representing that the commuter pass is used going from S to T, the third from T to S, and the four layer representing that the pass has already been used. However, when using the code below I only passed subtask 3, which only puts a constraint on N. Can anyone help to take a look as I am pretty sure that the time complexity is near O(NlogN).
Here is my code:
#include <bits/stdc++.h>
#define int long long
#define INF 1e16
#define pi pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int maxN = 1e5+5;
struct cmp{
bool operator() (pi a, pi b){
return a.fi > b.fi;
}
};
int N,M,S,T,U,V,res;
vector<pi> adj[maxN]; //original graph
vector<pi> adj2[maxN<<2]; //4-layered graph
int distS[maxN],distT[maxN];
void dijk(int dist[], int src){
for(int i = 1; i <= N; ++i)dist[i] = INF;
bool vis[maxN];
memset(vis,false,sizeof(vis));
priority_queue<pi,vector<pi>,cmp> Q;
Q.push(pi(0,src));
dist[src] = 0;
while(!Q.empty()){
pi p = Q.top(); Q.pop();
int d = p.fi; int loc = p.se;
if(vis[loc])continue;
vis[loc] = true;
for(auto x: adj[loc]){
if(dist[loc] + x.se < dist[x.fi]){
dist[x.fi] = dist[loc] + x.se;
if(!vis[x.fi]){
Q.push(pi(dist[x.fi],x.fi));
}
}
}
}
}
//for dijkstra on the layered graph
int dist[maxN<<2];
bool vis[maxN<<2];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
freopen("../test.in","r",stdin);
cin >> N >> M >> S >> T >> U >> V;
for(int i = 1; i <= M; ++i) {
int a, b, c;
cin >> a >> b >> c;
adj[a].pb(pi(b,c));
adj[b].pb(pi(a,c));
//layer 1 to layer 1
adj2[a].pb(pi(b,c));
adj2[b].pb(pi(a,c));
//layer 1 to layer 2, enter into forward commuter pass (S->T)
adj2[a].pb(pi(N+a,0));
adj2[b].pb(pi(N+b,0));
//layer 1 to layer 3, enter into backward commuter pass (T->S)
adj2[a].pb(pi(2*N+a,0));
adj2[b].pb(pi(2*N+b,0));
//layer 1 to layer 4, for skipping commuter pass
adj2[a].pb(pi(3*N+a,0));
adj2[b].pb(pi(3*N+b,0));
//layer 2 to layer 4, exiting commuter pass
adj2[N+i].pb(pi(3*N+i,0));
//layer 3 to layer 4, exiting commuter pass
adj2[2*N+i].pb(pi(3*N+i,0));
//layer 4 to layer 4
adj2[3*N+a].pb(pi(3*N+b,c));
adj2[3*N+b].pb(pi(3*N+a,c));
}
dijk(distS,S);
dijk(distT,T);
for(int i = 1; i <= N; ++i){
for(auto x: adj[i]){
if(distS[i] + x.se + distT[x.fi] == distS[T]){
//Ensures edge x is a part of a shortest path from S to T
//this edge must be from S->T and not T->S
//layer 2 to layer 2
adj2[N+i].pb(pi(N+x.fi,0));
//layer 3 to layer 3
adj2[2*N+x.fi].pb(pi(2*N+i,0));
}
}
}
//dijk for adj2, src = U
for(int i = 1; i <= 4*N; ++i)dist[i] = INF;
memset(vis,false,sizeof(vis));
priority_queue<pi,vector<pi>,cmp> Q;
Q.push(pi(0,U));
dist[U] = 0;
while(!Q.empty()){
pi p = Q.top(); Q.pop();
int loc = p.se;
if(vis[loc])continue;
vis[loc] = true;
for(auto x: adj2[loc]){
if(dist[loc] + x.se < dist[x.fi]){
dist[x.fi] = dist[loc] + x.se;
if(!vis[x.fi]){
Q.push(pi(dist[x.fi],x.fi));
}
}
}
}
cout << dist[3*N+V] << '\n';
}