提交记录

#include<bits/stdc++.h>
#define ll long long
#define mk(a,b) make_pair(a,b)
#define rd(a) a=read()
using namespace std;
ll n,choice[20],jiyin[(1<<18)][20];
long double jiyi[(1<<18)][20];
bool o[20];
struct dott{long double x,y;int id;}d[20],k;

ll read(){
	ll x=0,sign=1;char c=getchar();
	while(!(c>='0'&&c<='9')){if(c=='-')sign=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*sign;
}

long double dis(int x,int y){return sqrt((d[x].x-d[y].x)*(d[x].x-d[y].x)+(d[x].y-d[y].y)*(d[x].y-d[y].y));}

void dfs(int x,int ge,ll ya,long double sp){
	if(ge==n){jiyi[ya][x]=0;jiyin[ya][x]=0;return;}
	
	long double minn=2e17,mi=2e17;ll mih=0;
	for(int i=1;i<=n;++i){
		if(!o[i]){
			ll yasuo=ya+(1<<(i-1)),dist=dis(x,i);
			if(jiyin[yasuo][i]){
				minn=min(minn,jiyi[yasuo][i]+sp);
				if(jiyi[yasuo][i]+dist<mi){
					mi=jiyi[yasuo][i]+dist;mih=i;
				}
			}else{
				o[i]=1;
				dfs(i,ge+1,yasuo,sp+dist);
				o[i]=0;
				minn=min(minn,jiyi[yasuo][i]+sp);
				if(jiyi[yasuo][i]+dist<mi){
					mi=jiyi[yasuo][i]+dist;mih=i;
				}
			}
		}
	}
	jiyi[ya][x]=mi;jiyin[ya][x]=mih;
	return;
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	
	rd(n);
	for(int i=1;i<=n;++i){
		cin>>d[i].x>>d[i].y;d[i].id=i;
		if(k.y<d[i].y)k=d[i];
	}
	
	o[k.id]=1;
	dfs(k.id,1,(1<<(k.id-1)),0);
	
	ll ya=0;
	for(int i=k.id;i;i=jiyin[ya][i]){
		cout<<i<<" ";
		ya+=(1<<(i-1));
	}
	
	
	return 0;
}
/*

*/