Help me identify the reason for wrong answer in a basic graph problem(893C).

Revision en1, by levi.ackerman1732, 2020-01-31 09:08:18

893C - Rumor

Hello all

I am trying to solve this question. I came up with a certain procedure, which to me seems right. Let me know if you find a mistake in it. Thanks.

My approach: I have assumed that I am starting from Node 0. I have joined paths from this node to all the other nodes with the given cost(input). For the neighbouring nodes input I have stored such that they do not have any cost to traverse between them, and I have also stored them in a separate vector(say v1) to use them later.

I have used Dijkstra's Algorithm to find the Shortest path from Node 0 to all the other nodes.

Now using v1 I have maintained an additional variable sum to all the additional distances that I need not cover.

I have then added the shortest distances that I found using Dijkstra and subtracted the sum of additional distances.

It works fine for most cases but fails at test case 11. The logic to me seems infallible. Help me with that.

I am extremely sorry If I am missing that is something fairly obvious.

69879696

Tags #dfs and similar, #graphs, #greedy

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English levi.ackerman1732 2020-01-31 09:08:18 1138 Initial revision (published)