misschuer

常用链接

统计

积分与排名

百事通

最新评论

旅行商简化版

 1#include <iostream>
 2#include <cmath>
 3#include <algorithm>
 4using namespace std;
 5
 6struct node
 7{
 8    double x;
 9    double y;
10}; 
11
12double dist(node a , node b)
13{
14    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
15}
16
17bool comp(node a , node b)
18{
19    return a.x < b.x;
20}
21
22double dp[ 1001 ][ 1001 ] , temp;
23node q[ 1001 ];
24
25int main()
26{    
27    int n , i , j , k;
28    dp[ 1 ][ 1 ] = 0; 
29    
30    cin >> n;
31       
32       for (i = 1 ; i <= n  ; ++ i)
33           cin >> q[ i ].x >> q[ i ].y;
34       
35       sort (q + 1 , q + n + 1 , comp);
36       
37       for (i = 2 ; i <= n ; ++ i)
38           dp[ i ][ 1 ] = dp[i - 1][ 1 ] + dist(q[ i ] , q[i - 1]);
39             
40       for (i = 3 ; i <= n ; ++ i)
41           for (j = 2 ; j < i ; ++ j)
42           {
43               if (i == j)
44               {
45                   dp[ i ][ j ] = dp[ i ][i - 1] + dist(q[ i ] , q[i - 1]);
46                   continue;
47               }
48               
49               if (i > j + 1)
50               {
51                   dp[ i ][ j ] = dp[i - 1][ j ] + dist(q[ i ] , q[i - 1]);     
52                   continue;
53               }
54               
55               if (i == j + 1)
56                   for (k = 1 ; k < j ; ++ k)
57                   {
58                       if (k == 1)
59                       {
60                           dp[ i ][ j ] =  dp[ j ][ k ] + dist(q[ i ] , q[ k ]);
61                           continue;
62                       }
63                       temp = dp[ j ][ k ] + dist(q[ i ] , q[ k ]);
64                       if (temp < dp[ i ][ j ])
65                           dp[ i ][ j ] = temp;
66                   }
67           }
68           dp[ n ][ n ] = dp[ n ][n - 1] + dist(q[n - 1] , q[ n ]);
69           printf ("%.2f\n" , dp[ n ][ n ]);
70           return 0;
71}

posted on 2009-04-28 18:01 此最相思 阅读(272) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理