You are not logged in. Please login at www.codechef.com to post your questions!

×

KNGPRB – Editorial

2
2

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.

This question is marked "community wiki".

asked 07 Aug '18, 00:27

horsbug98's gravatar image

4★horsbug98
3436
accept rate: 21%

edited 09 Aug '18, 15:37

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,236
×850
×180
×94
×83
×6

question asked: 07 Aug '18, 00:27

question was seen: 281 times

last updated: 09 Aug '18, 15:37