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

×

how to solve this problem based on graph and counting from hackerearth?

asked 20 Aug '17, 11:38

arpit728's gravatar image

1★arpit728
6831562
accept rate: 10%

@vijju123

Try this out.

(20 Aug '17, 18:44) arpit7281★

Its out of my scope atm dear. I am yet to implement djikstra.

(20 Aug '17, 19:02) vijju123 ♦♦4★

Hey @arpit728,

It's clear that we need to use Dijkstra's algorithm to solve this problem because Dijkstra's algorithm finds the shortest distance from the root to other nodes in O(|E|+|V|log |V|) time. But the question asks us to find the number of ways path can be chosen.

Now when you are applying Dijkstra's algorithm, we have to take another variable array where we are going to store the number of paths we have come across with the smallest path. After we know what is the number of paths required to reach each node than applying the rule of multiplication in combination. Multiply all the values in the array.

let's take an example:

1->2 1

2->3 3

1->3 2

so now when we start applying Dijkstra's algo from index 1 other distances are infinite, now mark index 1 as visited and index 2 is at distance of 1 and index 3 is at a distance of 2 from 1. so our array would be 1, and then we go to 2 and than again min distance to 3 is same before so we increase the value of array to 2. at last 3 is also visited.

array - [1,1,2]

multiply all the values and you get the answer as 2

Hope this helps!

Pre requisite- Dijkstra's algorithm.

link

answered 20 Aug '17, 19:40

sandeep_007's gravatar image

5★sandeep_007
7997
accept rate: 16%

https://www.youtube.com/watch?v=rBvFMJLYAbs

see this....it's good !

one part i didn't understand that why we are adding 1 to our count_Arr instead of count[intermediate]...if you understand it then please help me also :)

link

answered 20 Aug '17, 20:06

pk301's gravatar image

3★pk301
62710
accept rate: 16%

Replying to @pk301 (since it is too long for a comment)

gkcs says that "...we need to find the number of ways to get to 1, multiply that by the number of ways we can get to 2, multiply that by the number of ways to get to 3, and so on and so forth..." and then says that he stores these number of ways in the count array, however this is NOT correct.
If we truly were finding the "number of ways to get to" each vertex, we would be adding count[intermediate]. What we require to find in this problem, and what we are storing in count[v], is not the total number of ways to get to some vertex v, but rather the number of vertices from which we can get to v such that the total distance travelled to v is the shortest possible. I hope it makes sense now.

link

answered 21 Aug '17, 04:58

meooow's gravatar image

6★meooow ♦
7.0k718
accept rate: 48%

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,650
×1,197
×164
×150
×126
×125

question asked: 20 Aug '17, 11:38

question was seen: 567 times

last updated: 21 Aug '17, 04:58