gistfile1.cpp

#include <fstream>
#include <cmath>
#include <iomanip>//precision
using namespace std;
#define  infnty  150000;
class point
{
public:
	double x,y;
};

int array[150][150];
double dist[150][150];
double mdist[150];
point pt[150];
int	N;

int main()
{
	ifstream fin("cowtour.in");
	ofstream fout("cowtour.out");
	
	fin>>N;
	for (int i=0;i<N;i++)
	{
		fin>>pt[i].x>>pt[i].y;
	}

	char ignore_enter = fin.get();
	for (int i=0;i<N;i++)
	{
		for (int j = 0 ; j<N;j++)
			array[i][j] = fin.get()-'0';
		char ignore_line = fin.get();
	}
	//Floyd-Warshall
	//init..
	for (int i=0;i<N;i++)
	{
		for (int j=0;j<N;j++)
		{
			if(i==j) dist[i][j] = 0;

			else if (array[i][j])
			{
				dist[i][j] = (pt[i].x-pt[j].x)*(pt[i].x-pt[j].x)+(pt[i].y-pt[j].y)*(pt[i].y-pt[j].y);
				dist[i][j] = sqrt(dist[i][j]);
			}
			else
			{
				dist[i][j] = 150000;
			}
		}
	}
	//floyd-warshall
	for (int k = 0;k<N;k++)
	{
		for(int i =0;i<N ;i++)
		{
			for(int j=0;j<N;j++)
			{
				if (dist[i][k]+dist[k][j]<dist[i][j])
				{
					dist[i][j] = dist[i][k]+dist[k][j];
				}
			}
		}
	}
	//
	double mmdist = 0;
	for (int i=0;i<N;i++)
	{
		double max_j = 0;
		for (int j =0 ; j<N ;j++)
		{
			if (dist[i][j]>max_j&&dist[i][j]<150000)
			{
				max_j = dist[i][j];		
			}
		}
		mdist[i] = max_j ;
		if (mdist[i]>mmdist)
		{
			mmdist = mdist[i];
		}
	}
	
	double min_res = 150000;
	for (int i=0 ;i<N; i++)
	{
		for (int j=0 ;j<N ;j++)
		{
			if (dist[i][j]==150000)
			{
				double tempdist =(pt[i].x-pt[j].x)*(pt[i].x-pt[j].x)+(pt[i].y-pt[j].y)*(pt[i].y-pt[j].y);
				tempdist = sqrt(tempdist);
				if (tempdist+mdist[i]+mdist[j]<min_res)
				{	
					min_res = tempdist+mdist[i]+mdist[j];
				}
			}
		}
	}
	fout<<setiosflags(ios::fixed);
	fout<<setprecision(6)<<max(mmdist,min_res)<<endl;
	fin.close();
	fout.close();
	return 0;
}