记录编号	127354	评测结果	AAAAAA
题目名称	[USACO 2.4.3]牛的旅行	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2014-10-15 15:51:20	内存使用	0.93 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
queue<int> A;
char s[160];
int zuox[151]={0},zuoy[151]={0},n,m,lian[151][151]={0},jihe[151][151]={0},to[151][151]={0},jiheshu,i,p,j,k,zj1;
bool pan[151]={0};
long long zj2,zj3;
double zui=1e10,qwq,street[151][151]={0},zhi[151][151]={0},ENDzhi[151]={0};
void init()
{
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d%d",&zuoy[i],&zuox[i]);
	for(i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		for(p=1;p<=n;p++)
		if(s[p]!='0')
		{
			lian[i][0]++;
			lian[i][ lian[i][0] ]=p;
			to[i][0]++;
			to[i][ to[i][0] ]=p;
			zj2=zuox[i]-zuox[p];zj2*=zj2;
			zj3=zuoy[i]-zuoy[p];zj3*=zj3;
			zj2+=zj3;
			qwq=sqrt((double)zj2);
			street[i][p]=qwq;
		}
	}
}
void bfs_set()
{
	for(i=1;i<=n;i++)
	if(!pan[i])
	{
		pan[i]=true;
		jiheshu++;
		jihe[jiheshu][0]=1;
		jihe[jiheshu][1]=i;
		A.push(i);
		while(!A.empty())
		{
			zj1=A.front();A.pop();
			for(p=1;p<=lian[zj1][0];p++)
			if(!pan[ lian[zj1][p] ])
			{
				pan[ lian[zj1][p] ]=true;
				jihe[jiheshu][0]++;
				jihe[jiheshu][ jihe[jiheshu][0] ]=lian[zj1][p];
				A.push(lian[zj1][p]);
			}
		}
	}
}
void Set_SPFA()
{
	for(i=1;i<=jiheshu;i++)
	for(p=1;p<=jihe[i][0];p++)
	{
		for(j=1;j<=jihe[i][0];j++)
		zhi[ jihe[i][p] ][ jihe[i][j] ]=1e10;
		zhi[ jihe[i][p] ][ jihe[i][p] ]=0;
	}
	for(i=1;i<=jiheshu;i++)
	for(p=1;p<=jihe[i][0];p++)
	{
		zj1=jihe[i][p];
		for(j=1;j<=to[zj1][0];j++)
		{
			A.push(to[zj1][j]);
			zhi[zj1][ to[zj1][j] ]=street[zj1][ to[zj1][j] ];
		}
		while(!A.empty())
		{
			k=A.front();A.pop();
			for(j=1;j<=to[k][0];j++)
			if(zhi[zj1][ to[k][j] ]>zhi[zj1][k]+street[k][ to[k][j] ])
			{
				zhi[zj1][ to[k][j] ]=zhi[zj1][k]+street[k][ to[k][j] ];
				A.push(to[k][j]);
			}
		}
		for(j=1;j<=jihe[i][0];j++)
		if(zhi[zj1][ jihe[i][j] ]>ENDzhi[zj1])
		ENDzhi[zj1]=zhi[zj1][ jihe[i][j] ];
	}
}
void End_find()
{
	for(i=1;i<=jiheshu;i++)
	for(p=i+1;p<=jiheshu;p++)
	for(j=1;j<=jihe[i][0];j++)
	for(k=1;k<=jihe[p][0];k++)
	{
		zj2=zuox[ jihe[i][j] ]-zuox[ jihe[p][k] ];zj2*=zj2;
		zj3=zuoy[ jihe[i][j] ]-zuoy[ jihe[p][k] ];zj3*=zj3;
		zj2+=zj3; qwq=sqrt((double)zj2);
		qwq+=ENDzhi[ jihe[i][j] ]+ENDzhi[ jihe[p][k] ];
		if(qwq<zui) zui=qwq;
	}
}
int main()
{
	freopen("cowtour.in","r",stdin);
	freopen("cowtour.out","w",stdout);
	init();
	bfs_set();
	Set_SPFA();
	End_find();
	printf("%.6lf\n",zui);
	return 0;
}