UVa 10724

From Algorithmist
Jump to navigation Jump to search

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