REVERSE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Dmytro Berezin
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu

DIFFICULTY:

Easy

PREREQUISITES:

Graph, Shortest Path Algorithms

PROBLEM:

A directed graph with N vertices and M edges is given.
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?
1 ≤ N,M ≤ 105

EXPLANATION:

Add reverse edge of each original edge in the graph. Give reverse edge a weight=1 and all original edges a weight of 0. Now, the length of the shortest path will give us the answer.

How?

If shortest path is p: it means we used k reverse edges in the shortest path. So, it will give us the answer.
The shortest path algorithm will always try to use as less reverse paths possible because they have higher weight than original edges.

To find shortest path, we can use Dijkstra’s Algorithm which works in O(|E| log |V|) if implemented using adjacency lists and priority queue.
Also, since there are only 0 and 1 weight edges, we can also do this by BFS: maintain a deque instead of a queue and add a vertex to the front of the deque if 0 edge is used and to the back of the deque otherwise.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

16 Likes

@darkshadows Could you please explain the deque solution more: what do we do after adding the edges as said?

@ambarpal
Study this - Geeks For Geeks Dijsktra Adjacency List

@ambarpal, there is not much difference between deque and queue. You take vertices from the beginning each time but to deque you can add to the beginning sometimes if the weight of edge is 0 (because there is no difference which vertices of the same level to explore firstly).

1 Like

Please help me in this code
http://www.codechef.com/viewsolution/4545769

Can someone help me in finding the bug http://www.codechef.com/viewsolution/4503656

Can someone please provide the test case where this solution is failing.http://ideone.com/7347aF

I am storing the undirected version of graph in a vector and applying dijkstra’s finding the shortest path keeping the track of the minimum number of edges to be reversed by checking if the edge (i,j) exists in the input graph(stored in a set).

Is it giving TLE because of the way of implementation?

can someone tell me how we can give the weight of reverse edges as 1 when we dont how many such reverse are possible and even if it is possible then how???

A O(V+E) algorithm: Combination of dfs and bfs. Basically in this algo we use dfs to push nodes into the bfs queue… Initially all the nodes which can be visited from vertex node 1 are pushed into the queue with level being equal to 0… Then each time we dequeue and do the dfs of all the elements(if not already visited) which can be visited by reversing the edge with this vertex(This pushes them into the queue) .The level of all these nodes will be level of the dequeued node+1…Do this until the queue empties.The level of the nth node is the answer if it is visited otherwise it is -1.

i have used warshalls algorithm to find the shortest path but my solution gave a wa

i took a 2d matrix and initially i stored INF in matrix then
matrix[x][y]=0; and matrix[y][x]=1;
then i applied kruskals algo
which gave coreect answers for the given test case but wa when i submitted my solution .

A simple question how you get the thought for this like adding a reverse edge with weight 1 this makes the problem very easy. Is this a classical problem or i can use any other apporoach to solve this…please help.

Can any one give me test cases for which my code is giving WA…

Thnx for ur help…

http://www.codechef.com/viewsolution/4491750

Why is your modifies bfs working faster than Djiktra algorithm?
Here are my two solution using bfs(http://www.codechef.com/viewsolution/4560098) and using Djiktsta (http://www.codechef.com/viewsolution/4557359)

I tried implementing the method suggested by @asheshvidyut in Python. The result is here : http://www.codechef.com/viewsolution/4563220.
However, I exceed the time limit. I also rewrote the code with a merge to make it faster (but less readable), but I still get a TLE : http://www.codechef.com/viewsolution/4563280.

Am I doing something wrong or is Python inherently too slow ?

can some one please check this
http://www.codechef.com/viewsolution/4832243
and tell me where i did the mistake

Solution

Question

Can anyone help me why my code fails on this question?
Thank you!

I tried to submit this in D, and got a SISEGV!. Here’s the link to my submission: codechef.com/viewsolution/10597167
Then I just translated the same code to C++, and it was accepted!!!:
Here’s the link: codechef.com/viewsolution/10598114
The D version executed fine on my system (gdc 5.1). Can anyone please explain???

I have use dijkstra but getting tle can anybody help me in finding the reason
https://www.codechef.com/viewsolution/11997317

I have use dijkstra but getting tle can anybody help me in finding the reason
https://www.codechef.com/viewsolution/11997317

Hi @ambarpal I have done it by BFS using a queue. Here is my solution for reference : http://www.codechef.com/viewsolution/4482761 . In the solution graph vector is the input graph and ans[i] stores the length of the shortest path from N to that node so far. It is updated if we find a shorter path. ans[1] will finally store the shortest length from n to 1.