Problem link: CodeChef: Practical coding for everyone
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<vector> adj(N,vector());
vector dist(N);
int n,m;
void add_edge(int u,int v,int w)
{
adj[u].push_back({v,w});
}
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();
for(auto opt:adj[curr_node])
{
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;
for(int i=1;i<=n;i++) adj[i].clear();
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;
add_edge(p.first,p.second,0);
if(!present[{p.second,p.first}]) add_edge(p.second,p.first,1);
}
dijsktra(1);
cout<<(dist[n]>=INF ? -1 : dist[n])<<'\n';
return;
}
int main()
{
fastio();
int t=1;
// cin>>t;
while(t–) solve();
return 0;
}