1.20 Tue
LG P1522
牧场：联通的牧区；牧场的直径：任意两个牧区的距离（最短路）的最大值；目的是连接两个牧场，使得新的大牧场的直径最小，输出的新的直径
1.肯定先求连通块
2.\(N\leq 150\) 且要求任意两个点之间的最短路，所以用 floyd
3.考虑一个新连通块（原来有 \(A,B\) 两个牧场，连了一条 \(i\rightarrow j,\ i\in A, j\in B\) 的边）直径的情况：
①.原来 \(A\) 牧场的直径
②.原来 \(B\) 牧场的直径
③. \(i\rightarrow j\) 的边权 + \(i\) 在 \(A\) 连通块里能达到最远的距离 + \(j\) 在 \(B\) 连通块里能达到的最远距离