Problem 1350 --算法实现题 3-15 双调旅行售货员问题（习题 3-23）

1350: 算法实现题 3-15 双调旅行售货员问题（习题 3-23）

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $3$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 动态规划

Description

欧氏旅行售货员问题是对给定的平面上 n 个点确定一条连接这 n 个点的长度最短的哈密顿回路。由于欧氏距离满足三角不等式，所以欧氏旅行售货员问题是一个特殊的具有三角不等式性质的旅行售货员问题。它仍是一个 NP 完全问题。最短双调 TSP 回路是欧氏旅行售货员问题的特殊情况。平面上 n 个点的双调 TSP 回路是从最左点开始，严格地由左至右直到最右点，然后严格地由右至左直至最左点，且连接每一个点恰好一次的一条闭合回路。
算法设计：

给定平面上 n 个点，计算这 n 个点的最短双调 TSP 回路。

Input

输入第 1 行有 1 个正整数 n，表示给定的平面上的点数。接下来的 n 行中，每行 2 个实数，分别表示点的 x 坐标和 y 坐标。

Output

将计算的最短双调 TSP 回路的长度（保留 2 位小数）输出

Sample Input复制

7
0 6
1 0
2 3
5 4
6 1
7 5
8 2

Sample Output复制

25.58
1 3 4 6 7 5 2 1

推荐代码 查看1350 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战 梅子晗2 329904 2018-11-25 19:17:11

赛题来源/所属竞赛 NA 算法导论(第三版)中文完整高清版

竞赛编号 竞赛名称 竞赛时间 访问比赛