Problem name: Chef and Reversing Problem link: https://www.codechef.com/problems/REVERSE Problem statement: Sometimes mysteries happen. Chef found a directed graph with N vertices and M edges in his kitchen! The evening was boring and chef has nothing else to do, so to entertain himself, Chef thought about a question "What is the minimum number of edges he needs to reverse in order to have at least one path from vertex 1 to vertex N, where the vertices are numbered from 1 to N.

Doubt: Greetings everyone, I am trying to solve this problem, I got all the logic and i have coded the problem too, but I have come across a situation in the given code, this code gives an WA, but if I uncomment Line '1' and comment the Line '2', it gives a AC, can anybody please help me understand the issue

My logic for this is to firstly mark all given edges u->v as true in the map, and then traverse the entire map then I add the edge u->v with a weight of 0, but if v->u is not present in the map, then I add v->u with a weight of 1

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;
    //add_edge(u,v,0); // Line 1  ***********************************
}

for(auto x:present)
{
    pii p=x.first;
    add_edge(p.first,p.second,0); // Line 2  ************************
    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;

}