题目：牛的旅行

思路：
先预处理出两点间的距离，跑一边floyd，然后处理出每个点到离它最远的和它连通的距离L[i]。
然后再对于每个点，枚举所有和它不连通的点j，用L[i]+L[j]+d(i,j)更新最小答案。
注意下，一个牧场的最长路径有可能比L[i]+L[j]+d(i,j)长。

代码：

#include<bits/stdc++.h>
using namespace std;#define maxn 150
#define db double
#define read(x) scanf("%d",&x)int n;
int X[maxn+5],Y[maxn+5];
db a[maxn+5][maxn+5];db L[maxn+5];int main() {read(n);for(int i=1;i<=n;i++) read(X[i]),read(Y[i]);for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) {int x;scanf("%1d",&x);if(x==0) {if(i!=j) a[i][j]=2e9;}else a[i][j]=sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]));}for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=min(a[i][j],a[i][k]+a[k][j]);db ans=2e9,ans_=0;for(int i=1;i<=n;i++) {for(int j=1;j<=n;j++) if(a[i][j]<2e9) L[i]=max(L[i],a[i][j]);ans_=max(ans_,L[i]);}for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i][j]>=2e9) ans=min(ans,L[i]+L[j]+sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j])));printf("%.6lf",max(ans_,ans));return 0;
}