UVa 10793

From Algorithmist
Jump to: navigation, search

10793 - The Orc Attack[edit]

Summary[edit]

This is a straight-forward Graph Theory/Shortest Path problem.

Given L locations, you have to find a point such that it meets the following contraint:

  • Is equidistant from point 1 to point 5.

If there is more than one meeting that constraint, resolve by:

  • Minimize the farthest point from each of the points.

Explanation[edit]

Run an all-pairs Shortest Path algorithm on the graph to obtain the full distance matrix, and then the rest is trivial.

Gotcha's[edit]

  • The point will have to be able to reach every single point. (This is only attainable if the graph is fully connected.)
  • If there is no such point (or if the graph is disconnected), output -1.
  • There might be more than one path from u to v - choose the shortest one.

Input[edit]

3
7 11
1 7 2
2 7 2
3 7 2
5 7 2
6 7 1
1 6 1
2 6 1
3 6 1
4 6 1
5 6 1
7 6 1
6 1
1 2 3
7 5
1 6 1
2 6 1
3 6 1
4 6 1
5 6 1

Output[edit]

Map 1: 1
Map 2: -1
Map 3: -1