用的DP,但发现最小值都算错了，求调awa

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
	double x,y;
	int id;
}a[1005],l[1005],r[1005];
double maxk=-1e9;
int tot1,tot2,k;
double f[1005][1005][2];
bool cmp1(node xx,node yy){
	if(xx.y==yy.y){
		return xx.x>yy.x;
	}
	return xx.y>yy.y;
}
bool cmp2(node xx,node yy){
	if(xx.y==yy.y){
		return xx.x<yy.x;
	}
	return xx.y>yy.y;
} 
double dis(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
int stk[1005],top;
void dfs(int x,int y,double p){
	if(x==0 && y==0)return;
	if(x==0){
		stk[++top]=r[y].id;
		dfs(x,y-1,p);
		return;
	}
	if(y==0){
		stk[++top]=l[x].id;
		dfs(x-1,y,p);
		return;
	}
	if(p==f[x][y][0]){
		stk[++top]=l[x].id;
		if(f[x][y][0]==f[x-1][y][0]+dis(l[x].x,l[x].y,l[x-1].x,l[x-1].y)){
			dfs(x-1,y,f[x-1][y][0]);
		}else{
			dfs(x-1,y,f[x-1][y][1]);
		}
	}else{
		stk[++top]=r[y].id;
		if(f[x][y][1]==f[x][y-1][1]+dis(r[y].x,r[y].y,r[y-1].x,r[y-1].y)){
			dfs(x,y-1,f[x][y-1][1]);
		}else{
			dfs(x,y-1,f[x][y-1][0]);
		}
	}
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
		a[i].id=i;
		if(a[i].y>maxk){
			maxk=a[i].y;
			k=i;
		}
	} 
//	cout<<k<<endl;
	for(int i=1;i<=n;i++){
		if(i==k) continue;
		if(a[i].x<a[k].x){
			l[++tot1]=a[i];
		}else{
			r[++tot2]=a[i];
		}
	}
	sort(l+1,l+tot1+1,cmp1),sort(r+1,r+tot2+1,cmp2);
//	for(int i=1;i<=tot1;i++)cout<<l[i].id<<" "<<l[i].y<<endl;
//	cout<<endl;
//	for(int i=1;i<=tot2;i++)cout<<r[i].id<<" "<<r[i].y<<endl;
//	cout<<endl;
	for(int i=0;i<=tot1;i++){
		for(int j=0;j<=tot2;j++){
			f[i][j][0]=1e18;
			f[i][j][1]=1e18;
		}
	}
	f[0][0][0]=0;
	f[0][0][1]=0;
	if(tot1>0) f[1][0][0]=dis(l[1].x,l[1].y,a[k].x,a[k].y);
	if(tot2>0) f[0][1][1]=dis(r[1].x,r[1].y,a[k].x,a[k].y);
	for(int i=0;i<=tot1;i++){
		for(int j=0;j<=tot2;j++){
			if(i==j && i==0)continue;
			if(i==1 && j==0)continue;
			if(j==1 && i==0)continue;
			if(i==0){
				f[i][j][1]=f[i][j-1][1]+dis(r[j-1].x,r[j-1].y,r[j].x,r[j].y);
			}else{
				if(j==0){
					f[i][j][0]=f[i-1][j][0]+dis(l[i-1].x,l[i-1].y,l[i].x,l[i].y);
				}else{
					f[i][j][1]=min(f[i][j-1][1]+dis(r[j-1].x,r[j-1].y,r[j].x,r[j].y),f[i][j-1][0]+dis(l[i].x,l[i].y,r[j].x,r[j].y));
					f[i][j][0]=min(f[i-1][j][1]+dis(r[j].x,r[j].y,l[i].x,l[i].y),f[i-1][j][0]+dis(l[i-1].x,l[i-1].y,l[i].x,l[i].y));
				}
			}
		}
	}
//	cout<<f[1][1][1]<<endl;
	if(f[tot1][tot2][1]>f[tot1][tot2][0]){
		dfs(tot1,tot2,f[tot1][tot2][0]);
	}else{
		dfs(tot1,tot2,f[tot1][tot2][1]);
	}
//	cout<<min(f[tot1][tot2][1],f[tot1][tot2][0]);
	cout<<k<<" ";
	while(top){
		cout<<stk[top]<<" ";
		top--;
	}
	return 0;
}