12 人解决，39 人已尝试。
42 份提交通过，共有 666 份提交。
7.6 EMB 奖励。
单点时限: 20.0 sec
内存限制: 256 MB
旅行商问题问题（Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。
它是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。
所谓NP困难问题，意思是到目前为止还找不到能够在多项式的时间内求解最短回路的算法。
然而，在现实生活中的旅行商问题，很多情况下我们并不需要求得最精确的最短回路，如果某一个解足够接近事实上的最优解，我们也认为这个解是可以接受的，并把它看做最优解。
下面要求你不管你用什么方法，求解TSP问题，只要足够接近事实上的最优解，我们都认为是正确的答案。
你有最多20秒的时间。
例如，快递小哥送快递的时候，所有快递站的分布如样例所示，如果在这个城市中访问每一个快递站一次并回到起始点的最短回路长度是147km，但实际上快递小哥用某个TSP算法求解出的是150千米，相对于整个城市的规模来说，我们认为150千米也是一个最优解。
第 $1$ 行是一个整数 $n \leqslant 150$。
后面 $n$ 行，每行 $3$ 个正整数，分别表示城市的编号、城市x坐标、y坐标。
只有一个数，可以是整数或者浮点数，表示TSP求解得到的最短回路的长度。
3 1 1 0 2 2 0 3 3 0
4.0
10 1 0 0 2 12 32 3 5 25 4 8 45 5 33 17 6 25 7 7 15 15 8 15 25 9 25 15 10 41 12
149.54092413044515 （事实上的最优解是147.34084656774644）
只要足够接近最优解就认为正确。
12 人解决，39 人已尝试。
42 份提交通过，共有 666 份提交。
7.6 EMB 奖励。