题目大意：
有n个点，一个人要从最左边的点走到最右边的点再走回来，除了起点每个点都只能走一次，求最短路径长度
思路：
首先可以看做是两个人一起走且路径无任何重合
设dp(i,j) 表示两个人走了前i个点，一个人在点i，另一个在点j
特殊的状态为j=i-1时，此时j可以一步跳到i+1，特殊考虑
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 #include<vector> 7 #include<queue> 8 #include<algorithm> 9 #define inf 2147483611 10 #define ll long long 11 #define MAXN 1010 12 #define MOD 13 using namespace std; 14 inline int read() 15 { 16 int x=0,f=1; 17 char ch;ch=getchar(); 18 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} 19 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} 20 return x*f; 21 } 22 struct node 23 { 24 double x,y; 25 }a[MAXN]; 26 double dis(node a,node b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));} 27 int n; 28 double dp[MAXN][MAXN],ans; 29 int main() 30 { 31 while(scanf("%d",&n)!=EOF) 32 { 33 for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y); 34 ans=2147483647.0; 35 dp[2][1]=dis(a[1],a[2]); 36 if(n==1) ans=0.0;if(n==2) ans=dp[2][1]; 37 for(int i=3;i<=n;i++) 38 { 39 for(int j=1;j<i;j++) 40 { 41 if(j!=i-1) dp[i][j]=dp[i-1][j]+dis(a[i-1],a[i]); 42 if(j==i-1) 43 { 44 dp[i][i-1]=2147483647.0; 45 for(int k=1;k<i-1;k++) 46 dp[i][i-1]=min(dp[i][i-1],dp[i-1][k]+dis(a[k],a[i])); 47 } 48 if(i==n) ans=min(ans,dp[i][j]+dis(a[j],a[n])); 49 } 50 } 51 printf("%.2lf ",ans); 52 } 53 }