asd.rar_旅行售货员

#include<stdio.h> #include<math.h> #include<limits.h> #define swap(x,y) {x=x^y;y=x^y;x=x^y;} #define min(x,y) x<y?x:y #define maxn 101 FILE *in_stream; FILE *out_stream; struct { int x,y; }a[maxn]; double d[maxn][maxn],p[maxn][maxn]; int n; void init() { int i; scanf("%d",&n); for (i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y); } void qsort(int l,int r) { int i=l,j=r,mid=a[(i+j)>>1].x; while (i<j) { while (a[i].x<mid) i++; while (mid<a[j].x) j--; if (i<=j) { swap(a[i].x,a[j].x); swap(a[i].y,a[j].y); i++; j--; } } if (l<j) qsort(l,j); if (i<r) qsort(i,r); } double cnt(int x1,int y1,int x2,int y2) { int x=(x1-x2)*(x1-x2); int y=(y1-y2)*(y1-y2); return sqrt(x+y); } void work_p() { int i,j; for (i=1;i<n;i++) for (j=i+1;j<=n;j++) p[i][j]=p[j][i]=cnt(a[i].x,a[i].y,a[j].x,a[j].y); } void DP() { int i,j; d[1][1]=0; for (i=2;i<=n;i++) d[i][1]=p[i][1]; for (i=2;i<n;i++) { d[i+1][i]=INT_MAX; for (j=1;j<=i-1;j++) { d[i+1][j]=d[i][j]+p[i][i+1]; d[i+1][i]=min(d[i+1][i],d[i][j]+p[j][i+1]); } } } int main() { in_stream = fopen("input.txt","r"); out_stream = fopen("output.txt","w"); init(); qsort(1,n); work_p(); DP(); printf("%.2lf",d[n][n-1]+p[n][n-1]); fclose(in_stream); fclose(out_stream); return 0; }