2437: [C++一本通-图论算法]例4-2 牛的旅行

信息学奥赛一本通 2. 数据结构 第4章 图论算法 3.最短路径 例4-2 牛的旅行 【问题描述】 农民John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。 但是就目前而言，你能看到至少有两个牧区不连通。现在，John 想在农场里添加一条路径（注意, 恰好一条）。 对这条路径有限制：一个牧场的直径就是牧场路径中最远两个牧区的距离（本题中提到的距离都指的是最短距离）。 现在请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后,这个更大的新牧场有最小的直径。 注意：如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。

第 1 行：一个整数 N (1<=N<=150), 表示牧区数； 第 2 到 N+1 行：每行两个整数 X,Y(0<=X,Y<=100000)，表示 N 个牧区的坐标，每个牧区的坐标都是不一样的。 第 N+2 行到第 2*N+1 行:每行包括 N 个数字 (0 或 1)，表示一个对称邻接矩阵。 输入数据中至少包括两个不连通的牧区。

只有一行，包括一个实数，表示所求答案。数字保留六位小数。

8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010

22.071068