#O1056. 旅行商问题
旅行商问题
题目描述
有 个城市,编号 , 表示城市 到 的距离(保证对称且 )。从城市 出发,每个城市恰好经过一次,最后停在任意城市,求最小的总路程。
题目类型
状态压缩动态规划
输入格式
第一行一个整数 。
接下来 行,每行 个整数,表示距离矩阵。
输出格式
一行一个整数,表示最小总路程。
样例 #1
样例输入 #1
3
0 1 2
1 0 3
2 3 0
样例输出 #1
4
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 城市数 | |
| 距离 |
- 表示已访问集合 、当前在 的最小路程,复杂度 。