usaco_cowtour.cpp

usaco自己做的1到5章的代码

/*
ID: wangyuc2
PROG: cowtour
LANG: C++
*/
#include <fstream>
#include <iostream>
#include <cmath>
#include <memory>
#include <iomanip>

using namespace std;
ifstream fin("cowtour.in");
ofstream fout("cowtour.out");
struct Node{
     int  x;
     int  y;
     };
double dis(Node a,Node b)
{
       return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}
int main()
{   
    double a[150][150];
    int i,j,k,t;
    double rm[150];
    Node point,p[150];
    char ch;
    double min,max1,max2,maxp;
    fin>>k;
    for(i=0;i<k;i++)
        fin>>p[i].x>>p[i].y;
    for(i=0;i<k;i++)
      for(j=0;j<k;j++)
      {
         fin>>ch;
         if(ch=='1')  a[i][j]=dis(p[i],p[j]);
         else a[i][j]=0;
         //else a[i][j]=0xFFFFFFFF;
      }
    max1=0;
    for(t=0;t<k;t++)
      for(i=0;i<k;i++)
      {//if(t==i) continue;
      for(j=0;j<k;j++)
      {
		  if(t==i || t==j || i==j) continue;
          if(a[i][t]!=0 && a[t][j]!=0)
			  if(a[i][j]>a[i][t]+a[t][j] || a[i][j]==0) a[i][j]=a[i][t]+a[t][j];
         // if(max1<a[i][j]) max1=a[i][j];
      }
    }
    for(i=0;i<k;i++){maxp=0;
      for(j=0;j<k;j++)
      {
          if(a[i][j]!=0 && a[i][j]>maxp) maxp=a[i][j];
      }
      rm[i]=maxp;
      if(maxp>max1) max1=maxp;
    }
    maxp=0xffffffff;
    for(i=0;i<k;i++){
      for(j=0;j<k;j++)
      if(i!=j && a[i][j]==0)
      {
          if(maxp>rm[i]+rm[j]+dis(p[i],p[j])) maxp=rm[i]+rm[j]+dis(p[i],p[j]);
      }
    }
   // cout.setf(out.showpoint);
    fout.precision(6);
    fout.setf(ios::fixed);
    fout<<(maxp>max1?maxp:max1)<<endl;
   // system("PAUSE");
    return 0;
}