'''
Travelling Salesman Problem（TSP）问题
什么是TSP
    简单来说，Travelling Salesman Problem (TSP) 是最基本的路线问题。
    它寻求的是旅行者由起点出发，通过所有给定的需求点后，再次返回起点所花费的最小路径成本，
    也叫旅行商问题、旅行推销员问题、货郎担问题……

假设现在有四个城市，它们分别是0，1，2，3，他们之间往来的代价如下图所示：
C = [
     [0,3,6,7],
     [5,0,2,3],
     [6,4,0,2],
     [3,7,5,0]
]
现在要从城市0出发，最后又回到0，期间1，2，3都必须并且只能经过一次，使代价最小。

事实上，这是一个最基本的TSP问题，且构成最优子结构性质，所以可以使用动态规划求解，
下面来验证一下此方法求解的可行性:

设 s，s1，s2…s为满足题意的最短回路。假设从s到s1的路径已经确定，则问题转化为从s1到s2...再到s的最短路径问题。
而很显然，s1，s2…s一定可以构成一条最短路径，所以构成最优子结构性质，可以用动态规划求解。

明确问题可解，那下一步就是列方程求解了。

[简单推导一下动态规划方程]：
用 V' 表示一个点的集合，假设从顶点 s 出发， d(V', i), 表示当前到达顶点 i，经过 V' 集合中所有顶点一次的最小花费。
   1.当 V' 为仅包含起点的集合，也就是：
      d ({ s }, s) = 0 ，即从起点 s 出发经过只有 s 的点集到达 s 点的代价为0。
   2.其他情况，则对子问题求最优解。需在 V' 这个城市集合中，尝试每一个城市结点，并求出最优解。
      d(V' + {j}, j) = min(d(V', k) + C[k][j]), (k属于V')
      即从起点 s 出发，经过包含点j的点集 V' 中的点且仅经过一次，到达点 j 的最短代价为：
      从起点 s 出发，经过包含点 k 的点集 V' 中的点且仅经过一次，先到达点 k 的代价，和再直接从K点到达j点的代价之后的最小值。

   3.最后的求解方程式为:
      Answer = min(d(V', k) + C[k][s]), (k属于V'， s为起点)

[状态压缩DP]
所谓状态压缩，就是利用二进制以及位运算来实现对于本来应该很大的数组的操作。
而求解动态规划问题，很重要的一环就是状态的表示，一般来说，一个数组即可保存状态。
但是有这样的一些题目，它们具有DP问题的特性，但是状态中所包含的信息过多，如果要用数组来保存状态的话需要四维以上的数组。
于是，我们就需要通过状态压缩来保存状态，而使用状态压缩来保存状态的DP就叫做状态压缩DP。

例题TSP的动态规划方程中，V’ 是一个集合，而对于集合的状态表示最简单的办法就是利用set，
但是这个时候就要考虑一个问题，在代码实现的时候，我们不能用一个集合去做一个数组的下标。
自然而然，我们想到可以利用集合的特征值，但这个方法很复杂，而且不容易实现。

但是通过位运算，可以用一个二进制数来存储这个集合。如 十进制的数字 15，即1111(2)，就可表示四个顶点都在的点集V'。
简单来说就是——如果城市 k 在集合 V’ 中，那么存储集合的变量 i 的第 k 位就为 1，否则为 0。
由于有 n 个城市，所有的状态总数我们用 M 来表示，那么很明显：
M = 2^n，而 0 到 2^n -1 的所有整数则构成了 V’ 的所有状态。
这样，结合位运算，动归方程的状态表示就很容易了。

[位运算]：
异或 ( xor )：
相同为 0，不同为 1。
例如：
1 xor 1 = 0，0 xor 0 = 0，
1 xor 0 = 1，0 xor 1 = 1；
它的运算满足交换律以及结合律。

左移 ( left shift )， 右移 ( right shift )，相当于对于二进制数的位置移动。
例如10001(2) 左移 1，就是10001(2)左移一位，变成了100010(2)，换算成十进制，相当于扩大了 2 倍，同理右移则是缩减两倍。
那么对于任意的一个二进制数，左移 k 位就是乘 2k, 右移就是整除 2k 。

[实例分析]：
将以上思路可以用二维动态规划数组表现出来，即 dp[i][j], 其中 i 代表点集 V', j表示目前到达的顶点，
则dp[i][j]表示从起点 s 出发，经过点集 i 中的各个顶点仅且一次，并到达顶点 j 的最小代价。
1. 因为d ({ s }, s) = 0 ，即从起点 s 出发经过只有 s 的点集到达 s 点的代价为0,
   所以 dp[1][0] = 0；
2. 其他情况，有：
   i 取值 1 到 2^n - 1 来表示有 n 个点的所有点集 V' 的可能情况(从 1 开始取是因为一定要从起点 0 出发) ,
   j 取值 1 到 (n-1) 来表示最后回到起点 s 前所到达的顶点, 所以 j 的值不能为起点 0。
     并且用 i & (1<<j) 来判断顶点 j 是否在点集 i 里，值为 1 则存在。
   k 取值 0 到 (n-1)，表示到达 j 点前的顶点，可以取 0 是因为有可能从起点直接到 j 点，并且 k 一定要在 i 中。
   因为最后 j 点是要被加入到点集 i 中的，所以一开始的时候不让 j 存在于 i 中，即：
       dp[i|(1<<j)][j] = min(dp[i|(1<<j)][j], dp[i][k] + c[k][j])
   而最终结果则为：
      对于取值为 1 到 M(即 2^n -1)的顶点 j， 看总的代价的最小值。
      min(dp[M - 1][j] + c[i][j])
   [注]：因为最后比的是最小值min, 所以除了 dp[1][0] = 0 ，其他的初始取值都为inf。

'''
class Solution:
    def tsp(self, c):
        n = len(c)
        m = 2**(n)
        dp = [[float('inf')]*n for _ in range(m)]
        dp[1][0] = 0
        res = float('inf')
        for i in range(1, m):
            for j in range(1, n):
                if i&(1<<j): continue # j后面是要加入i的，这里不能重复
                for k in range(n):
                    if i&(1<<k): # i中必须得包括k
                        dp[i|(1<<j)][j] = min(dp[i|(1<<j)][j], dp[i][k] + c[k][j])
        for j in range(1,n):
            res = min(res, dp[m-1][j] + c[j][0])
        return res
