记录编号	584702	评测结果	AAAAAAA
题目名称	[USACO 2.4.3]牛的旅行	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-11-14 17:26:47	内存使用	0.00 MiB

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
	int x,y;
}po[155];
int fa[155];
double f[155][155],dpo[155],dpa[155];
double ans=0x3f3f3f3f;
double dis(double p1x,double p1y,double p2x,double p2y){
	return sqrt((p1x-p2x)*(p1x-p2x)+(p1y-p2y)*(p1y-p2y));
}
int get(int x){
	if(fa[x]==x){
		return x;
	}
	return fa[x]=get(fa[x]);
}
void merge(int x,int y){
	fa[get(x)]=get(y);
}
bool chk(int x,int y){
	return get(x)==get(y);
}
int main(){
	freopen("cowtour.in","r",stdin);
	freopen("cowtour.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>po[i].x>>po[i].y;
		fa[i]=i;
	}
	string tmp;
	for(int i=1;i<=n;i++){
		cin>>tmp;
		for(int j=1;j<=n;j++){
			if(i==j){
				f[i][j]=0;
			}
			else{
				if(tmp[j-1]=='0'){
					f[i][j]=0x3f3f3f3f;
				}
				else{
					f[i][j]=dis(po[i].x,po[i].y,po[j].x,po[j].y);
					merge(i,j);
				}
			}
		}
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(chk(i,j)){
				dpo[i]=max(dpo[i],f[i][j]);
			}
		}
		dpa[get(i)]=max(dpa[get(i)],dpo[i]);
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(!chk(i,j)){
				ans=min(ans,max(dpo[i]+dpo[j]+dis(po[i].x,po[i].y,po[j].x,po[j].y),max(dpa[get(i)],dpa[get(j)])));
			}
		}
	}
	cout<<setiosflags(ios::fixed)<<setprecision(6);
	cout<<ans<<endl;
	return 0;
}