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 ${\displaystyle n}$. Weight of an edge (when it exists) is equal to the distance between points.

Find a pair of vertices ${\displaystyle (u,v)}$, such that:

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

Explanation

A simple ${\displaystyle 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 ${\displaystyle (u,v)}$. For each pair compute ${\displaystyle C_{u,v}}$ from its definition.

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

${\displaystyle min(d_{i,j},\ d_{i,u}+w_{u,v}+d_{v,j},\ d_{i,v}+w_{v,u}+d_{u,j})}$

where ${\displaystyle w_{u,v}}$ is the straight-line distance between vertices ${\displaystyle u}$ and ${\displaystyle 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