rt，代码如下，真的要似了。

不知是我转移策略错误还是细节写挂，请大佬指出 qwq

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define tp tuple<int,int,int>
const int inf=1e16,maxn=1e3+10;
struct node{
    int id;
    double x,y;
}scan[maxn],ls[maxn],rs[maxn];
double f[maxn][maxn][2];
//f[i][j][0/1]为左边扩展了i个节点，右边扩展了j个节点，现在在左边/右边的最小距离值
tp bef[maxn][maxn][2];
//bef[i][j][k]存储一个三元组，代表最小的f[i][j][k]由f[g0(i,j,k)][g1(i,j,k)][g2(i,j,k)]转移而来
double kpow(double p){
    return p*p;
}
double dist(int a,int b){
    return sqrt(kpow(scan[a].x-scan[b].x)+kpow(scan[a].y-scan[b].y));
}
void update(int i,int j,int k,int ni,int nj,int nk,double pos){
    if(f[i][j][k]>f[ni][nj][nk]+pos){
        f[i][j][k]=f[ni][nj][nk]+pos;
        bef[i][j][k]={ni,nj,nk};
    }
}
int res[maxn];
bool operator == (tp a,tp b){
    return get<0>(a)==get<0>(b) and get<1>(a)==get<1>(b) and get<2>(a)==get<2>(b); 
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int n;cin>>n;
    int k=0;
    double maxs=-inf;
    for(int i=1;i<=n;i++){
        double p,q;cin>>p>>q;
        scan[i]={i,p,q};
        if(maxs<q){
            maxs=q;
            k=i;
        }
    }
    int ltot=0,rtot=0;
    for(int i=(k-1==0?n:k-1);i!=k;i=(i-1==0?n:i-1)){
        if(scan[i].x<scan[k].x){
            break;
        }
        rs[++rtot]=scan[i];
    }
    for(int i=(k+1==n+1?1:k+1);i!=k;i=(i+1==n+1?1:i+1)){
        if(scan[i].x>=scan[k].x){
            break;
        }
        ls[++ltot]=scan[i];
    }
    //上面是在处理在k左边/在k右边的点，分别存到ls/rs里面
    //f[i][j][0/1]为左边扩展了i个节点，右边扩展了j个节点，现在在左边/右边的最小距离值
    for(int i=0;i<=ltot;i++){
        for(int j=0;j<=rtot;j++){
            f[i][j][0]=f[i][j][1]=inf;
        }
    }
    f[0][0][0]=f[0][0][1]=0;
    for(int len=1;len<=ltot+rtot;len++){
        for(int i=0;i<=len;i++){
            int j=len-i;
            if(i>0)update(i,j,0,i-1,j,0,dist(ls[i-1].id,ls[i].id)),update(i,j,0,i-1,j,1,dist(rs[j].id,ls[i].id));
            if(j>0)update(i,j,1,i,j-1,1,dist(rs[j-1].id,rs[j].id)),update(i,j,1,i,j-1,0,dist(ls[i].id,rs[j].id));
        }
    }
    //f[i][j][0/1]为左边扩展了i个节点，右边扩展了j个节点，现在在左边/右边的最小距离值
    double ans=f[ltot][rtot][0];
    tp st={ltot,rtot,0};
    if(ans>f[ltot][rtot][1]){
        ans=f[ltot][rtot][1];
        st={ltot,rtot,1};
    }
    int tot=0,lt=ltot,rt=rtot;
    while(st!=(tp){0,0,0} and st!=(tp){0,0,1}){
        tot++;
        if(get<2>(st)){
            res[tot]=rs[rt].id;rt--;
        }
        else res[tot]=ls[lt].id,lt--;
        st=bef[get<0>(st)][get<1>(st)][get<2>(st)];
    }
    res[++tot]=k;
    for(int i=tot;i>=1;i--)cout<<res[i]<<" ";
	return 0;
}