## USACO chapter 2 section 2.4 Cow Tours

```USER: tian tianbing [tbbd4261]
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.
submission #2 for this problem.  Congratulations!

/*ID:tbbd4261PROG:cowtourLANG: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;}
```

posted on 2010-08-03 13:57 田兵 阅读(150) 评论(0)  编辑 收藏 引用 所属分类: USACO

 < 2010年8月 >
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

• 随笔 - 65
• 文章 - 2
• 评论 - 17
• 引用 - 0

•

• 积分 - 27201
• 排名 - 652