# UVa 10724

## Summary

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

Find a pair of vertices $(u,v)$ , such that:

• $u .
• The edge $(u,v)$ isn't present in the graph.
• $C_{u,v}=\sum _{i=1}^{n}\sum _{j=i+1}^{n}(d_{i,j}-d'_{i,j})$ is maximized. $d_{i,j}$ is the shortest distance between vertices $i,j$ in the original graph. $d'_{i,j}$ is the shortest distance between them, when the edge $(u,v)$ is added to the graph.
• $C_{u,v}>1$ • 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 $u$ , and smaller $v$ .

## Explanation

A simple $O(n^{4})$ algorithm is enough to get accepted. First, use Floyd-Warshall to compute the shortest distances in the original graph, and then check all pairs $(u,v)$ . For each pair compute $C_{u,v}$ from its definition.

The shortest path between vertices $i$ and $j$ after the edge $(u,v)$ is added is equal to:

$min(d_{i,j},\ d_{i,u}+w_{u,v}+d_{v,j},\ d_{i,v}+w_{v,u}+d_{u,j})$ where $w_{u,v}$ is the straight-line distance between vertices $u$ and $v$ .

## Input

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

No road required
1 3
1 3