Coding is the closest thing we have to superpower !

3860 : 状压dp-环游世界
描述

有n个地方(标号1到n),要从标号为0的地方出去,经过所有的地方之后回来(同一个地方可以经过多次),求最短的时间。

已知(n+1)*(n+1)的矩阵a,a[i][j]表示顶点i到顶点j所需要的时间(a[i][i]=0)。

输入

第一行输入一个整数n(1≤n≤10)。

接下来n + 1行,每行n + 1个整数,表示矩阵中的元素,矩阵中的元素在区间[1, 1000]内(除a[i][i])。

输出

输出最短时间。

样例

输入

3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0

输出

8
标签
语言:
主题: