# UVa 10793

Jump to navigation
Jump to 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