3040 - 最短Hamilton路径
时间限制 : 1 秒
内存限制 : 128 MB
给定一个有权无向图，包括n个点，标记为0 ~ n-1，以及连接n个点的边，求从起点0到终点n-1的最短路径。要求必须经过所有点，而且只经过一次。
输入
第一行输入整数n。接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（记为a[i, j]）。 对于任意的x, y, z，数据保证 a[x, x]=0，a[x, y]=a[y, x] 并且 a[x, y]+a[y, z]>=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
提示
数据范围，1 ≤ n ≤ 20，0 ≤ a[i, j] ≤ 10^7。
来源
动规专题