P1522 [USACO2.4] Cow Tours

There are many pastures on Farmer John's farm. Some paths connect certain pairs of pastures. A set of all mutually connected pastures is called a field. However, at present you can see that at least two pastures are not connected by any path. Thus, Farmer John has multiple fields. John wants to add exactly one path. The path is subject to the following: The diameter of a field is the distance between the two farthest pastures in the field (all distances in this problem refer to shortest-path distances). Consider the following field with 5 pastures, where pastures are marked by `*` and paths are straight segments. Each pasture has its own coordinates: ```plain (15,15) (20,15) D E *-------* | _/| | _/ | | _/ | |/ | *--------*-------* A B C (10,10) (15,10) (20,10) ``` The diameter of this field is approximately $12.07106$, and the farthest two pastures are A and E, whose shortest path is $A \to B \to E$. Here is John's other field: ```plain *F(30,15) / _/ _/ / *------* G H (25,10) (30,10) ``` In this example, he has exactly these two fields. John will choose one pasture from $\{A,B,C,D,E\}$ and one pasture from $\{F,G,H\}$, and then connect them with a path so that the diameter of the new, larger field is as small as possible. Note that if two paths cross in the middle, we do not consider them connected. They are considered connected only if two paths meet at the same pasture. The input file includes the pastures, their coordinates, and a symmetric adjacency matrix like the following: ```plain 　 A B C D E F G H A 0 1 0 0 0 0 0 0 B 1 0 1 1 1 0 0 0 C 0 1 0 0 1 0 0 0 D 0 1 0 0 1 0 0 0 E 0 1 1 1 0 0 0 0 F 0 0 0 0 0 0 1 0 G 0 0 0 0 0 1 0 1 H 0 0 0 0 0 0 1 0 ``` Other adjacency matrices may use row and column indices instead of letters to denote each pasture. The input data does not include pasture names. The input file contains at least two pastures that are not connected. Write a program to add a single path connecting two pastures from two different fields so that, after adding this path, the diameter of the resulting field is minimized. Output the minimal possible diameter among all valid ways to connect the fields.

The first line contains an integer $N$ ($1 \leq N \leq 150$), the number of pastures. The next $N$ lines each contain two integers $X,Y$ ($0 \leq X ,Y \leq 10^5$), the coordinates of the $N$ pastures. Note that each pasture has distinct coordinates. The next $N$ lines each contain $N$ numbers representing the adjacency matrix $M$. The number in row $i$, column $j$ is $1$ if pasture $i$ and pasture $j$ are directly connected by a path, and $0$ otherwise. It is guaranteed that $M_{i,j} = M_{j,i}$.

Output a single line containing a real number, which is the required diameter. Keep six digits after the decimal point. Just print to six decimal places; do not perform any special rounding.

The sample corresponds to the situation described in the statement. The optimal solution is to connect pasture C and pasture G. After connecting, there is only one field in the graph. The diameter of this field is $A \to B \to C \to G \to F$, with length approximately $22.071068$. It can be proven that there is no better plan. USACO 2.4 Translated by ChatGPT 5