题意：

给出二维平面上的n个点，现在从最左端出发，到达最右端的点，再返回最左端的点，要求遍历所有点且路程最短。

思路：

这是一个双调欧几里得旅行商问题。双线程dp。

$dp[i][j]$：快的人走到i，慢的人走到j的最短路程(i>j)。

对于当前点，要不在走得快的人走的边上，要不在走得慢的人走的边上。

有状态转移方程：

在走得快的人走的边上：

$dp[i+1][j]=min(dp[i+1][j],dp[i][j]+dis(i,i+1))$。

在走得慢的人走的边上：

$dp[i+1][i]=min(dp[i+1][i],dp[i][j]+dis(j,i+1))$。

代码：

struct point
{
    int x,y;
}p[530];
double dp[530][530];
bool cmp(point a,point b)
{
    return a.x<b.x;
}
double dis(point a,point b)
{
    return sqrt(1.0*(a.x-b.x)*(a.x-b.x)+1.0*(a.y-b.y)*(a.y-b.y));
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%d%d",&p[i].x,&p[i].y);
        sort(p,p+n,cmp);
        memset(dp,0x7f,sizeof(dp));
        dp[0][0]=0;
        for(int i=1;i<=n;i++)
            dp[i][0]=dp[i-1][0]+dis(p[i],p[i-1]);
        for(int i=0;i<n;i++)
            for(int j=0;j<i;j++)
            {
                dp[i+1][j]=min(dp[i+1][j],dp[i][j]+dis(p[i],p[i+1]));
                dp[i+1][i]=min(dp[i+1][i],dp[i][j]+dis(p[j],p[i+1]));
            }
        double ans=1e18;
        for(int i=0;i<n-1;i++)
            ans=min(ans,dp[n-1][i]+dis(p[i],p[n-1]));
        printf("%.2f\n",ans);
    }
    return 0;
}