We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
And if after verifying that your algorithm is printing "0" instead of an infinite value for nodes that start and end on the same vertex, make sure that you haven't overlooked this requirement "If there are edges between the same pair of nodes with different weights, the last one (most recent) is to be considered as the only edge between them.", which simply means to override any edges with the one that comes next. Example, suppose you have the following edges w/ costs denoted as "[ start, end, cost ]":
[ 1, 4, 24 ]
[ 1, 4, 20 ]
[ 1, 4, 36 ]
You are to consider only the last instance of the repeated edge, in this case "[ 1, 4, 36 ]" and simply discard the rest. Assuming you are using "Floyd Warshall"'s algorithm to solve this problem, this overwriting step will naturally occur as you build your distance table as long as you parse your edges in the order that it comes in the input. I initially parsed the edges in reverse for silly reasons and failed tests 2 to 5 because of it.
As an aside, keep in mind that this is a directed graph "[ 1, 4, 36 ]" is not a repeated instance of "[ 4, 1, 36 ]", do not override these with each other!
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Floyd : City of Blinding Lights
You are viewing a single comment's thread. Return to all comments →
And if after verifying that your algorithm is printing "0" instead of an infinite value for nodes that start and end on the same vertex, make sure that you haven't overlooked this requirement "If there are edges between the same pair of nodes with different weights, the last one (most recent) is to be considered as the only edge between them.", which simply means to override any edges with the one that comes next. Example, suppose you have the following edges w/ costs denoted as "[ start, end, cost ]":
[ 1, 4, 24 ]
[ 1, 4, 20 ]
[ 1, 4, 36 ]
You are to consider only the last instance of the repeated edge, in this case "[ 1, 4, 36 ]" and simply discard the rest. Assuming you are using "Floyd Warshall"'s algorithm to solve this problem, this overwriting step will naturally occur as you build your distance table as long as you parse your edges in the order that it comes in the input. I initially parsed the edges in reverse for silly reasons and failed tests 2 to 5 because of it.
As an aside, keep in mind that this is a directed graph "[ 1, 4, 36 ]" is not a repeated instance of "[ 4, 1, 36 ]", do not override these with each other!