1 #include <algorithm>
2 #include <cmath>
3 #include <cstdio>
4 #include <cstring>
5 #include <deque>
6 #include <iostream>
7 #include <map>
8 #include <queue>
9 #include <set>
10 #include <stack>
11 #include <string>
12 #include <vector>
13 using namespace std;
14 typedef long long LL;
15 const int maxn = 18;
16 const double PI = acos(-1);
17 const int mod = 1e9 + 7;
18 using namespace std;
19 // 定义常量
20 const int INF = 0x3f3f3f3f;
21 #define sqr(x) ((x) * (x))
22 // 定义变量
23 int type; // type == 1 满秩矩阵格式, type == 2 二维坐标式
24 int s;
25 int N; // 城市结点数量
26 int init_point;
27 double dp[1 << maxn][maxn];
28 // 动态规划状态数组dp[i][j]，i表示集合V’，j表示当前到达的城市结点
29 double dis[maxn][maxn]; // 两个城市结点之间的距离
30 vector<int> path[1 << maxn][maxn];
31 double ans;
32 vector<int> ans_path;
33 // 定义结构体
34 struct vertex {
35 double x, y; // 城市结点的坐标
36 string id; // 城市结点的id
37 void input() {
38 cin >> id;
39 scanf("%lf %lf", &x, &y);
40 }
41 } node[maxn];
42
43 double Dist(const vertex &a, const vertex &b) {
44 return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
45 }
46
47 void init() { // 数据初始化
48 scanf("%d", &N);
49 for (int i = 0; i < N; i++)
50 node[i].input();
51 for (int i = 0; i < N; i++) {
52 for (int j = 0; j < N; j++)
53 dis[i][j] = Dist(node[i], node[j]); // 计算城市之间的距离
54 }
55 for (int i = 0; i < (1 << N); i++) {
56 for (int j = 0; j < N; j++)
57 dp[i][j] = INF,path[i][j].clear();
58 } // 初始化，除了dp[1][0]，其余值都为INF
59 ans = INF;
60 return;
61 }
62 //复杂度 2^N * N^2
63 void slove() {
64 int M = (1 << N);
65 // M就是第四部分所说的V’状态总数，1<<N表示2^N，总共有2^N种状态
66 dp[1][0] = 0;
67 path[1][0].push_back(0);
68 // 假设固定出发点为0，从0出发回到0的花费为0。TSP只要求是一个环路，所以出发点可以任选
69 for (int i = 1; i < M; i++) {
70 // 枚举V’的所有状态
71 for (int j = 1; j < N; j++) {
72 // 选择下一个加入集合的城市
73 if (i & (1 << j))
74 continue;
75 // 城市已经存在于V’之中
76 if (!(i & 1))
77 continue;
78 // 出发城市固定为0号城市
79 for (int k = 0; k < N; k++) {
80 // 在V’这个城市集合中尝试每一个结点，并求出最优解
81 if (i & (1 << k)) {
82 // 确保k已经在集合之中并且是上一步转移过来的结点
83 if(dp[i][k] + dis[k][j] < dp[(1 << j) | i][j]){
84 dp[(1 << j) | i][j] = dp[i][k] + dis[k][j];
85 path[(1 << j) | i][j] = path[i][k];
86 path[(1 << j) | i][j].push_back(j);
87 }
88 dp[(1 << j) | i][j] = min(dp[(1 << j) | i][j],
89 dp[i][k] + dis[k][j]); // 转移方程
90 } // 将j点加入到i集合中
91 }
92 }
93 }
94 for (int i = 0; i < N; i++){
95 if(dp[M - 1][i] + dis[i][0]< ans){
96 ans=dp[M - 1][i] + dis[i][0];
97 ans_path = path[M-1][i];
98 }
99 }
100 // 因为固定了出发点，所以要加上到城市0的距离。另外要从所有的完成整个环路的集合V’中选择，完成最后的转移
101 }
102 int main() {
103 #ifndef ONLINE_JUDGE
104 freopen("in.txt", "r", stdin);
105 #endif
106 init();
107 slove();
108 cout<<"TSP路径长度: "<<ans<<endl<<"TSP回路： ";
109 for(int i=0;i<ans_path.size();i++){
110 if(i)cout<<' ';
111 cout<<node[ans_path[i]].id;
112 }cout<<endl;
113 return 0;
114 }
