USACO chapter 2 section 2.4 Cow Tours

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;
}

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


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


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

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜