久久最新精品国产,91久久精品国产成人久久,观看国产综合久久久久鬼色欧美亚洲一区二区

旅行商簡化版

#include <iostream>
2

#include <cmath>
3

#include <algorithm>
4

using namespace std;
5

struct node
7

{
8

double x;
9

double y;
10

};
11

double 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

bool comp(node a , node b)
18

{
19

return a.x < b.x;
20

}
21

double dp[ 1001 ][ 1001 ] , temp;
23

node q[ 1001 ];
24

int main()
26

{
27

int n , i , j , k;
28

dp[ 1 ][ 1 ] = 0;
29

cin >> n;
31

for (i = 1 ; i <= n ; ++ i)
33

cin >> q[ i ].x >> q[ i ].y;
34

sort (q + 1 , q + n + 1 , comp);
36

for (i = 2 ; i <= n ; ++ i)
38

dp[ i ][ 1 ] = dp[i - 1][ 1 ] + dist(q[ i ] , q[i - 1]);
39

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

if (i > j + 1)
50

{
51

dp[ i ][ j ] = dp[i - 1][ j ] + dist(q[ i ] , q[i - 1]);
52

continue;
53

}
54

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 此最相思閱讀(274) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

misschuer

導航

公告

留言簿

隨筆分類

文章分類

隨筆檔案

文章檔案

閱讀排行榜

評論排行榜

常用鏈接

統計

積分與排名

百事通

最新評論

旅行商簡化版