题目链接：

 

这个题和uva 1658题目很像，只是加了一点，就是每个点都要走，刚开始，我以为可以直接拆点，用最小费用流。并不是这样。

题意：n个点，坐标给出，设计一条路线，从最左边的点，走到最右边的点，再回来，除最左边的点和最右边的点外，每个点有且经过一次。求最短距离。

 

分析：

可以转换一下，是两个人走不同的路线，从最左边的点走到最右边的点。然后d(i,j)表示第一个人在I,第二个人在j时，还需走多长的距离。

但是，这样的定义是很难状态转移的，修改一下。d(i,j)表示1~max(i,j)的点全部都走过，两个人的位置分别是I,j还需要走多远，这样就有d(i,j) = d(j,i),这里我们默认i>j。

状态转移，i,j;两个位置下一步一定有一个人走到i+1,假如走到I+2……这样i+1点就没有走过，不能表示该状态。

也就是说，转移方程就出来了d(i,j) 下一步只有两种决策，要么是i走到i+1，要么是j走到 I+1;

边界条件是d(n-1,j) = dist(n-1,n)+dist(j,n);所求的是dist(1,2) + dp(2,1);

 

#include 
      
       using namespace std;double x[55],y[55];double dist[55][55];double dp[55][55];int main(){    int n;    while(scanf("%d",&n)!=EOF) {        for(int i=1;i<=n;i++) {            scanf("%lf%lf",&x[i],&y[i]);        }        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]));            }        }        for(int i=n-1;i>=2;i--) {            for(int j=1;j