graph algorithms - all pairs shortest paths - floyd warshall
Another shortest path problem. As you can see in the problem description you have to find the minimum distance from locations 1-5 to all other locations other than 1-5. Then you have to pick the candidates, which are equidistant from these 5 locations. That location must be reachable from all the locations in the graph. If such a location exist, then pick the one which has the minimum farthest distance, that means this location( rally point ) is reachable from all other locations and has a minimum distance to all of them, there is a location that has the maximum minimum ( :-D ) distance from rally point, you have to pick a rally point that this value for that is minimum( distance to the farthest location ).
I simply construct the graph from input, run floyd-warshall on it, and the rest of the problem that has described and I just simulate it.
Subscribe to:
Post Comments (Atom)
-
Link to the problem on Timus Online Judge First of all there are two kinds of input which the answer is zero, first if sum % 2 == 1 or se... -
Link to the problem on Timus Online Judge The problem statement is completely straight forward with no hidden tricks :). Yeah yeah I know...
-
Link to the problem on Timus Online Judge This is a Computational Geometry problem. No 3 points lie on the same line and this is a great...
No comments:
Post a Comment