2921. 最短Hamilton路径
时间限制：1000 MS 内存限制：128 MB
题目描述
# 最短 Hamilton 路径 ## 题目描述 给定一张有 $n$ 个顶点的带权无向图，顶点编号为 $0$ 至 $n-1$。顶点之间的距离由矩阵 $a$ 给出，其中 $a[i,j]$ 表示顶点 $i$ 到顶点 $j$ 的距离。 请你求出从顶点 $0$ 出发、到顶点 $n-1$ 结束的最短 Hamilton 路径的长度。 Hamilton 路径是指恰好经过每个顶点一次的路径。路径的长度为路径上相邻顶点之间的距离之和。 当 $n=1$ 时，路径只包含顶点 $0$，长度为 $0$。 ## 输入格式 从文件 `hamilton.in` 中读入数据。 第一行包含一个整数 $n$，表示顶点个数。 接下来 $n$ 行，每行包含 $n$ 个整数，构成距离矩阵 $a$。其中第 $i+1$ 行的第 $j+1$ 个整数为 $a[i,j]$，顶点编号 $i,j$ 均从 $0$ 开始。 ## 输出格式 将答案输出到文件 `hamilton.out` 中。 输出一个整数，表示从顶点 $0$ 到顶点 $n-1$、恰好经过每个顶点一次的最短路径长度。 ## 数据范围 对于所有测试数据，保证： - $1 \le n \le 20$； - $0 \le a[i,j] \le 10^7$； - 对于任意 $0 \le x,y,z < n$，均有： - $a[x,x]=0$； - $a[x,y]=a[y,x]$； - $a[x,y]+a[y,z]\ge a[x,z]$。 答案不超过 $(n-1)\times 10^7$，可以使用有符号 $32$ 位整数存储。 ## 样例输入 ``` 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 ``` ## 资源限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$128$ MB。