PROBLEM LINK:
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.