最短Hamilton路径

【题目描述】

给定一个$n$个点的带权无向图，点从$0\sim n-1$标号，求起点 $0$ 到终点 $n-1$ 的最短Hamilton路径。 

Hamilton路径的定义是从 $0$ 到 $n-1$ 不重不漏地经过每个点恰好一次。

【输入格式】

第一行输入整数$n(1\leq n\leq 20)$。

接下来$n$行每行$n$个整数，其中第$i$行第$j$个整数表示点$i$到$j$的距离（记为$a(i,j)(0\leq a(i,j)\leq 10^7)$)。

对于任意的$x,y,z$，数据保证$a(x,x)=0,a(x,y)=a(y,x)$并且$a(x,y)+a(y,z)\geq a(x,z)$

【输出格式】

输出一个整数，表示最短Hamilton路径的长度。

【样例输入】

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

【样例输出】

18