# Need help with problem Chef and Reversing

Problem link: Contest Page | CodeChef
Problem name: Chef and Reversing

my logic is to add an edge of weight=1 only when it is needed that’s why i have used a map, but this results into a TLE, the main part which goes wrong is while populating the map and pushing egdes into the adjacency list, can anybody help me, and tell me where I am going wrong ?

My code:

#include <bits/stdc++.h>
using namespace std;
#define fastio()
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#define lli long long int
#define ll long long
#define pii pair<int,int>

int INF=1e9+1000;
int N=1e5+100;
vector dist(N);
int n,m;

{
}

void dijsktra(int src)
{
for(int i=1;i<=n;i++) dist[i]=INF;
priority_queue<pii,vector,greater> min_heap;
dist[src]=0;
min_heap.push({dist[src],src});

while(!min_heap.empty())
{
int curr_node=min_heap.top().second;
int curr_dist=min_heap.top().first;
min_heap.pop();
{
int next_node=opt.first;
int next_dist=opt.second;

if(curr_dist+next_dist<dist[next_node])
{
dist[next_node]=curr_dist+next_dist;
min_heap.push({dist[next_node],next_node});
}
}
}

return;

}

void solve()
{
cin>>n>>m;

map<pii,bool> present;
for(int i=0;i<m;i++)
{
int u,v; cin>>u>>v;
if(u==v) continue;
present[{u,v}]=true;
}

for(auto x:present)
{
pii p=x.first;
}

dijsktra(1);

cout<<(dist[n]>=INF ? -1 : dist[n])<<'\n';

return;

}

int main()
{
fastio();
int t=1;
// cin>>t;
while(t–) solve();

return 0;

}

Hey, instead of making a map, you can just make an adjacency list where you consider the weight of given edges as 0. Along with this, push the reverse of these edges considering their weight as 1. Then apply Dijkstra on it, traversing the adjacency list in linear time. With this you don’t need to check for every possible node if it exists or not. You can simply check for those nodes which you know are there. Even is there is a repetition of edge in the adjacency list it won’t cause a problem and will cut down the complexity by logN