# JOI 2018 Commuter Pass help

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;
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;
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;
//layer 1 to layer 1
//layer 1 to layer 2, enter into forward commuter pass (S->T)
//layer 1 to layer 3, enter into backward commuter pass (T->S)
//layer 1 to layer 4, for skipping commuter pass
//layer 2 to layer 4, exiting commuter pass
//layer 3 to layer 4, exiting commuter pass
//layer 4 to layer 4
}
dijk(distS,S);
dijk(distT,T);
for(int i = 1; i <= N; ++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
//layer 3 to layer 3
}
}
}
//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;
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';
}

``````

Problem solved.
For some reason changing

``````const int maxN = 1e5+5;
``````

to

``````const int maxN = 2e5+5;
``````

allowed me to AC despite the question stating that 2 <= N <= 100000