USER: tian tianbing [tbbd4261]
TASK: cowtour
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.011 secs, 3212 KB]
Test 2: TEST OK [0.000 secs, 3212 KB]
Test 3: TEST OK [0.000 secs, 3212 KB]
Test 4: TEST OK [0.000 secs, 3212 KB]
Test 5: TEST OK [0.022 secs, 3212 KB]
Test 6: TEST OK [0.022 secs, 3212 KB]
Test 7: TEST OK [0.032 secs, 3212 KB]
Test 8: TEST OK [0.032 secs, 3212 KB]
Test 9: TEST OK [0.022 secs, 3212 KB]
All tests OK.
Your program ('cowtour') produced all correct answers! This is your
submission #2 for this problem. Congratulations!
/*
ID:tbbd4261
PROG:cowtour
LANG:C++
*/
#include<fstream>
#include<iostream>
#include<cmath>
using namespace std;
ifstream fin("cowtour.in");
ofstream fout("cowtour.out");
const int MAX=160;
const double eps=1e-10, INT=1e30;
double dist[MAX][MAX]={0};
double dt[MAX]={0};
int locate[MAX][2]={0};
int n,i,j,k;
char t;
void Floyd()
{
for(k=1; k<=n; k++)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
if(dist[i][k]+dist[k][j]<dist[i][j])
dist[i][j]=dist[i][k]+dist[k][j];
}
for(i=1; i<=n; i++)
dist[i][i]=INT;
}
int main()
{
fin>>n;
for(i=1; i<=n; i++)
fin>>locate[i][0]>>locate[i][1];
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
fin>>t;
t=t-'0';
if(t)dist[i][j]=sqrt( (locate[i][0]-locate[j][0])*(locate[i][0]-locate[j][0])+
( locate[i][1]-locate[j][1])*(locate[i][1]-locate[j][1]) ) ;
else dist[i][j]=INT;
}
Floyd();
double pmax=0,max=0,pmin=INT,tt;
for(i=1; i<=n; i++)
{
pmax=0;
for(j=1; j<=n; j++)
if(dist[i][j]>pmax&&dist[i][j]!=INT)pmax=dist[i][j];
dt[i]=pmax;
if(pmax>max)max=pmax;
}
for(i=1; i<=n-1; i++)
for(j=i+1; j<=n; j++)
{
if(dist[i][j]==INT&&i!=j)
{
tt=sqrt((locate[i][0]-locate[j][0])*(locate[i][0]-locate[j][0])+
( locate[i][1]-locate[j][1])*(locate[i][1]-locate[j][1]) );
if(dt[i]+dt[j]+tt<pmin)pmin=dt[i]+dt[j]+tt;
}
}
fout.precision(6);
fout<<fixed<<(pmin>max?pmin:max)<<endl;
return 0;
}