本文共 769 字，大约阅读时间需要 2 分钟。

原题链接：

#include
   
    using namespace std;const int maxn=1e3+5;struct Point{       int x,y;}p[maxn];int n;double dis[maxn][maxn],res[maxn][maxn];double dp(int i,int j){       if(res[i][j]!=0.0)return res[i][j];    if(i==n-1)return res[i][j]=dis[n-1][n]+dis[j][n];    return res[i][j]=min(dp(i+1,j)+dis[i][i+1],dp(i+1,i)+dis[j][i+1]);}int main(void){       // freopen("in.txt","r",stdin);    while(~scanf("%d",&n)){           memset(res,0,sizeof(res));        for(int i=1;i<=n;i++)            scanf("%d%d",&p[i].x,&p[i].y);        for(int i=1;i<=n;i++)            for(int j=i+1;j<=n;j++)                dis[i][j]=dis[j][i]=sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));        printf("%.2f\n",dp(2,1)+dis[1][2]);    }    return 0;}