【题解】1343：牛的旅行

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 151
using namespace std;
double f[N][N],m[N],minx,r,temp,x[N],y[N],maxint=INF;
double dist(int i,int j){
	return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int main(){
	int i,j,n,k;
	char c;
	cin>>n;
	for(i=1;i<=n;i++)cin>>x[i]>>y[i];
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++){
			cin>>c;
			if(c=='1')f[i][j]=dist(i,j);
			else f[i][j]=maxint; 
		}
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(i!=j&&i!=k&&j!=k&&f[i][k]<maxint-1&&f[k][j]<maxint-1)
					if(f[i][j]>f[i][k]+f[k][j])
						f[i][j]=f[i][k]+f[k][j];
	memset(m,0,sizeof(m));
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(f[i][j]<maxint-1&&m[i]<f[i][j])m[i]=f[i][j];
	minx=INF;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j&&f[i][j]>maxint-1){
				temp=dist(i,j);
				if(minx>m[i]+m[j]+temp)minx=m[i]+m[j]+temp;
			} 
	for(i=1;i<=n;i++)if(m[i]>minx)minx=m[i];
	printf("%.6lf",minx);
	return 0;
}