记录编号	245662	评测结果	AAAAAA
题目名称	704.[USACO 2.4.3]牛的旅行	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-04-04 06:19:00	内存使用	0.00 MiB

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
namespace cat{
	const double INF=1e10;
	inline void read(int &x){
		x=0;char ch;
		while(ch=getchar(),ch<'!');
		while(x=10*x+ch-'0',ch=getchar(),ch>'!');
	}
	struct node{int x,y;}G[160];
	double w[155][155],a[155],r,ans=1e10;
	int n;
	double dis(int i,int j){
	       int x=G[i].x-G[j].x,y=G[i].y-G[j].y;
	       return sqrt(x*x+y*y);
	}    
	void floyed(){
	    int i,j,k;
	    for(k=1;k<=n;k++)
	        for(i=1;i<=n;i++)
	        if(i!=k)
	        	for( j=1;j<=n;j++)
	            if(j!=i)
	            if(w[i][j]>w[i][k]+w[k][j])w[i][j]=w[i][k]+w[k][j];
	    for(i=1;i<=n;i++)
	        for( j=1;j<=n;j++)
	        if(w[i][j]!=INF){
	            if(w[i][j]>a[i])a[i]=w[i][j];
	            if(w[i][j]>r)r=w[i][j];
	    	}
	}  
	int doo(){
		int i,j;char ch;
	    read(n);
	    for( i=1;i<=n;i++) read(G[i].x),read(G[i].y);
	     	for( i=1;i<=n;i++)
	        	for( j=1;j<=n;j++){
	             	ch=getchar();
	             	while(ch<'!') ch=getchar();
	            	if(ch=='1')w[i][j]=dis(i,j);
	            	else w[i][j]=INF;
	            }
	    floyed();
		double t;
	    for(i=1;i<=n;i++)
	    	for(j=1;j<=n;j++)
	        	if( i!=j&&w[i][j]==INF){
	            	t=dis(i,j)+a[i]+a[j];
					if(t<ans) ans=t;
	        	}
	    printf("%.6f",max(r,ans));
	    fclose(stdin);fclose(stdout);
	    return 0;
	}
}
FILE* ___=freopen("cowtour.in","r",stdin);
FILE* _=freopen("cowtour.out","w",stdout);
int ans= cat::doo();
int main(){;}