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.
No comments:
Post a Comment