这个代码用float过[scanf和printf用%f],而用double不过[scanf和printf改称%lf]


#define N 200
float DP[N][N];
struct Point {
  float x, y;
  Point(float _x=0.0,float _y=0.0):x(_x),y(_y){}
  bool operator<(const Point &a)const{return x<a.x;}
};

float
dist(const Point & a, const Point & b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

float
bitonic_eculidean_TSP(vector < Point > &raw)
{
  int n=(int)raw.size();
  sort(raw.begin(),raw.end());
  memset(DP,0,sizeof(DP));
  for(int i=1;i<n;i++)DP[i][0]=DP[i-1][0]+dist(raw[i],raw[i-1]);
  for(int i=2;i<n;i++){
    for(int j=1;j<i;j++){
      if((j+1)==i){
	DP[i][j]=DP[j][0]+dist(raw[i],raw[0]);
	for(int k=1;k<j;k++)
	  DP[i][j]=min(DP[i][j],DP[j][k]+dist(raw[i],raw[k]));
      }else if(i>j+1){
	DP[i][j]=DP[i-1][j]+dist(raw[i],raw[i-1]);
      }
    }
  }
  DP[n-1][n-1]=DP[n-1][0]+dist(raw[0],raw[n-1]);
  for(int i=1;i<=n-2;i++)DP[n-1][n-1]=min(DP[n-1][n-1],DP[n-1][i]+dist(raw[i],raw[n-1]));
  return DP[n-1][n-1];
}

int
main()
{
  int n;
  while(scanf("%d",&n)!=EOF){
    vector<Point>vp;
    float x,y;
    for(int i=0;i<n;i++){
      scanf("%f%f",&x,&y);
      vp.push_back(Point(x,y));
    }
    printf("%.2f\n",bitonic_eculidean_TSP(vp));
  }
}

• Re:这道题感觉很废,贴个代码。注意使用float不要使用double，至于为什么我也不知道...请各位大牛指教啊 (1382) PerfectCAI 2009-09-07 20:30:57
• Re:这道题感觉很废,贴个代码。注意使用float不要使用double，至于为什么我也不知道...请各位大牛指教啊 (19) 190181442 2011-07-07 09:42:44
• double应该用%lf读入，%f输出 (0) Ruby931031 2013-05-18 20:42:28