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

题目 大意：给一些点，让你从左到右，再从右到左，遍历所有的点，及一条哈密顿通路；

解题思路：状态转移方程：dp[ i ][ j ]=min{dp[ i ][ x  ]+dis[ x ][ j ]}（在j-i>1时，可x可直接为j-1）

#include<stdio.h>

#include<math.h> #include<iostream> #include<algorithm> using namespace std; #define MAXN 205 #define INF 1e200 struct Node{     double x;     double y; }node[MAXN]; double dis[MAXN][MAXN],dp[MAXN][MAXN]; bool cmp(struct Node a,struct Node b) {     return a.x<b.x; } inline double fun(Node a,Node b) {     return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2)); } int main() {     int N,i,j;     while(~scanf("%d",&N))     {         for(i=0;i<N;i++)             scanf("%lf%lf",&node[i].x,&node[i].y);         sort(node,node+N,cmp);         for(i=0;i<N;i++){             for(j=i;j<N;j++){                 dp[i][j]=INF;                 dis[i][j]=fun(node[i],node[j]);             }         }         dp[0][0]=0.0;dp[0][1]=dis[0][1];         N--;         for(i=0;i<N;i++){             for(j=0;j<i;j++)                 dp[i][i+1]=(dp[j][i]+dis[j][i+1]<dp[i][i+1])?(dp[j][i]+dis[j][i+1]):dp[i][i+1];             for(j=i+2;j<=N;j++)    dp[i][j]=dp[i][j-1]+dis[j-1][j];         }         printf("%0.2lf\n",dp[N-1][N]+dis[N-1][N]);     }     return 0; } /* 3 1 1 2 3 3 1 */

转载地址：http://ihuvi.baihongyu.com/