KNGPRB – Editorial

[horsbug98]

PROBLEM LINK:

Practice
Contest

Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh

DIFFICULTY:

MEDIUM

PREREQUISITES:

Graph, Dijkstra, Implementation

PROBLEM:

Given a directed graph, you need to find the minimum no of edges to be reversed to reach a destination vertex D from a source vertex S, or if it is unreachable.

QUICK EXPLANATION:

The cost of an edge which exists can be considered as 0 and the cost of a reverse edge of an existing edge can be considered as 1. While we are taking the input of the edges of the graph, we insert two edges in the graph, the given edge with weight 0 and a reverse edge with weight 1. Then we can simply apply Dijkstra algorithm and find the minimum distance of the destination from the source or if it cannot be reached.

EXPLANATION:

A directed graph is given. We consider the weights of the given edges as 0. Now we can see that making a bidirectional edge means to reverse the given edges(which are not useful for reaching the destination). While we take input of the edges, for each edge we input two edges, the given edge and a reverse edge of the given edge. We consider the weight of the given edge as 0 and the weight of the reverse edge as 1(as that edge does not exists from before but we put it). Now by applying Dijkstra algorithm we can find the minimum distance of the destination vertex from the source vertex, i.e. the minimum number of edges we have reversed. If the destination vertex is unreachable from the source vertex, then we simply output -1.

The time complexity of this approach is proportional to the number of edges and vertices in the given graph. Using a priority queue for the Dijkstra algorithm, the time complexity will be O(n + m*log(m)). Also you need to use fast input-output otherwise you might get a TLE. You can find the implementation below.

AUTHOR’S AND EDITORIALIST’S SOLUTIONS:

Author’s and editorialist’s solution can be found here.

[harshraj22]

Can you help me with my submissions ? I did the same thing which is explained in the editorial…

Edit : WTF !!! Adding ios_ and .tie(0) statements reduce the time so much !!!

[indiana_jones7]

why my code gives tle although i have used fastio and just the fact that i have used map instead of vector to store the graph

@indiana_jones7

why my code gives tle although i have used fastio and just the fact that i have used map instead of vector to store the graph
#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
int main() {
// your code goes heref
fastio
int t;
cin>>t;
while(t–)
{ int n,m;
priority_queue<pair<int,int>> q;
vector<pair<int,int>> mp[n+1];
cin>>n>>m;
int x,y;
bool vis[n+1]={false};
// cout<<vis[n]<<endl;
for(int i=0;i<m;i++)
{
cin>>x>>y;
mp[x].push_back({0,y});
mp[y].push_back({1,x});
}
vector d(n+1,INT_MAX);
int st,end;
cin>>st>>end;
d[st]=0;
q.push({0,st});
while(!q.empty())
{ // cout<<“visend”<<vis[end]<<endl;
int x=q.top().second;
// cout<<“x=”<<x<<endl;
q.pop();
if(vis[x])
continue;
vis[x]=true;

       //cout<<"gonna vis parent "<<x<<endl;
        for(auto it=mp[x].begin();it!=mp[x].end();it++)
        {  
            {
              // cout<<"inseert child"<<(*it).second<<endl;
             //   d[(*it).second]=min(d[(*it).second],d[x]+(*it).first);
              // cout<<"dist of chil="<<d[(*it).second]<<"its first="<<(*it).first<<endl;
              if(d[x]+(*it).first<d[(*it).second]){
                  d[(*it).second]=d[x]+(*it).first;
              
                 q.push({-d[(*it).second],(*it).second});}
                 
            }

        }
    }
        
        if(d[end]==INT_MAX)
        cout<<-1<<endl;
        else cout<<d[end]<<endl;
    
    
     
   
}
return 0;

}

[indresh584]

@horsbug98
Pls tell me why my code is giving WA
https://www.codechef.com/viewsolution/34071861