已知N个城市之间的相互距离，现有一推销员必须遍访这N个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？
用图论的术语来说，假设有一个图G = ( V , E ) ，其中V是顶点集合，E 是边集合，设D = [ d(i,j)
]是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $640$ | 正确数量 | $434$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 | 图论 |
已知N个城市之间的相互距离，现有一推销员必须遍访这N个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？
用图论的术语来说，假设有一个图G = ( V , E ) ，其中V是顶点集合，E 是边集合，设D = [ d(i,j)
]是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。
4
0 30 6 4
30 0 5 10
6 5 0 20
4 10 20 0
25
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$2 $ms] | 方子航 | 960408 | 2023-04-29 14:47:01 |
| 内存最少[$2064 $KB] | 安然 | 850415 | 2022-05-01 10:55:05 |
| 第一AC | 0x1701add | 592413 | 2020-06-08 17:25:10 |
| 第一挑战 | AOJ大管家 | 408852 | 2019-04-25 12:47:16 |
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|---|---|---|
| 1803 | 2023-2024-2学期<计算机专业竞赛实训> 第7-8周练习：图论算法【22计算机】 | 2024-04-08 00:00:00 | 请登录 |
| 1743 | 2022-2023-2学期<计算机专业竞赛实训> 第9-10周练习：图论算法【21计算机12345】 | 2023-04-17 00:00:00 | 请登录 |
| 1689 | 2021-2022-2学期<算法分析与设计> 第9-10周练习：图论算法 | 2022-04-18 08:00:00 | 请登录 |
| 1615 | 2020-2021-2学期<算法分析与设计> 第14-15周练习：图论算法 | 2021-05-17 00:00:00 | 请登录 |
| 1520 | 2019-2020-2学期<算法分析与设计>第11-12周练习：图论专题 | 2020-06-08 12:00:00 | 请登录 |