# UVa 10724

From Algorithmist

## 10724 - Road Construction[edit]

## Summary[edit]

Given is an undirected connected graph, which represents a city. Graph's vertices are points on 2D plane, numbered from 1 to . Weight of an edge (when it exists) is equal to the distance between points.

Find a pair of vertices , such that:

- .
- The edge isn't present in the graph.
- is maximized. is the shortest distance between vertices in the original graph. is the shortest distance between them, when the edge is added to the graph.
- When there are several pairs, satisfying above conditions, choose the one with smallest straight-line distance between vertices.
- If there's still a tie, favor a pair with smaller , and smaller .

## Explanation[edit]

A simple algorithm is enough to get accepted. First, use Floyd-Warshall to compute the shortest distances in the original graph, and then check all pairs . For each pair compute from its definition.

The shortest path between vertices and after the edge is added is equal to:

where is the straight-line distance between vertices and .

## Input[edit]

4 6 0 0 0 2 2 0 2 2 1 2 1 3 1 4 2 3 2 4 3 4 4 4 0 0 0 2 2 0 2 2 1 2 2 3 3 4 4 1 4 3 0 0 0 2 2 0 2 2 1 2 2 3 3 4 0 0

## Output[edit]

No road required 1 3 1 3