#O1056. 旅行商问题

旅行商问题

题目描述

有 nn 个城市,编号 0∼n−10 \sim n-1,di,jd_{i,j} 表示城市 ii 到 jj 的距离(保证对称且 di,i=0d_{i,i}=0)。从城市 00 出发,每个城市恰好经过一次,最后停在任意城市,求最小的总路程。

题目类型

状态压缩动态规划

输入格式

第一行一个整数 nn。

接下来 nn 行,每行 nn 个整数,表示距离矩阵。

输出格式

一行一个整数,表示最小总路程。

样例 #1

样例输入 #1

3
0 1 2
1 0 3
2 3 0

样例输出 #1

4

数据规模与约定

数据范围 说明
1≤n≤161 \le n \le 16 城市数
0≤di,j≤1060 \le d_{i,j} \le 10^6 距离
  • fS,if_{S,i} 表示已访问集合 SS、当前在 ii 的最小路程,复杂度 O(2nn2)O(2^n n^2)。