思路：走一圈可以轉(zhuǎn)化為兩個人同時從起點出發(fā)，沿兩條不同路走到終點。但如果用f(i)(j)表示第一個人走到i，第二個人走到j，還需走的距離，則由狀態(tài)（i，j）轉(zhuǎn)移時發(fā)現(xiàn)狀態(tài)轉(zhuǎn)移困難（例如，能否從i轉(zhuǎn)移到j，狀態(tài)中無法體現(xiàn)，也即無法保證兩人是否走到過同一點）。所以，轉(zhuǎn)換狀態(tài)表示：f(i)(j)表示1---max(i,j)全部走過，兩人分別在i、j時，還需走的距離。又因為f(i)(j)=f(j)(i)，所以，設i>j。但此時又因為如果從i轉(zhuǎn)移到i+1，i+2，i+3，........可能出現(xiàn)某些點并未走過的情況。所以，強制每次轉(zhuǎn)移時，兩人中只能有一人走到i+1點（此轉(zhuǎn)移不會導致漏解，如果第一人走到i+2，則可由第二人可走到i+1，以此類推）。所以，f(i)(j)只能轉(zhuǎn)移到f(i+1)(j)（第一個人走到i+1）、f(i+1)(i)（第二個人走到i+1）。則f(i)(j)=min{f(i+1)(j)+dist(i)(i+1),f(i+1)(i)+dist(j)(i+1)}（dist(i)(j)表示點i與點j之間的距離）。邊界：f(n-1)(j)（即最后一步）=dist(n-1)(n)（最后一步直接從n-1到n）+dist(j)(n)（最后一步直接從j到n）。

#include<set>#include<map>#include<cstdio>#include<cmath>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int maxn=1000+50;const int INF=0x3f3f3f3f;int n;int x[maxn],y[maxn];double f[maxn][maxn];double dist[maxn][maxn];void getDist(){    for(int i=1; i<=n; i++)    {        for(int j=1; j<=n; j++)        {            dist[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));        }    }}double solve(int i,int j){    if(f[i][j]!=INF) return f[i][j];    return f[i][j]=min(solve(i+1,j)+dist[i][i+1],solve(i+1,i)+dist[j][i+1]);}int main(){    while(scanf("%d",&n)!=EOF)    {        for(int i=1; i<=n; i++)        {            for(int j=1; j<=n; j++)                f[i][j]=INF;        }        for(int i=1; i<=n; i++)            scanf("%d%d",&x[i],&y[i]);        getDist();        for(int i=1; i<n-1; i++)            f[n-1][i]=dist[n-1][n]+dist[i][n];        printf("%.2f/n",solve(1,1));    }    return 0;}