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.
This problem has a fairly simple solution using connected components in undirected graphs. The answer to the problem is the summation of the minimum cost in each connected component, which can be computed using depth-first search. A boolean flag is needed for each node to indicate whether or not it has been connected to some component.
69901392