测绘星图

最左边的矿道越走越窄，最后变成仅供一人通过的裂缝。你们侧着身子挤过去，衣服被粗糙的岩壁刮得沙沙作响。CC的肩膀伤口被挤了一下，她闷哼一声，但没有停下。

裂缝尽头是一个巨大的地下空洞。洞顶悬挂着成千上万颗发光的水晶，像一片被冻结的星空。而在空洞中央的岩台上，摊着一张全息地图——不是纸张，而是一张由光线编织成的网，上面布满了节点和连线。

Echo的终端发出一阵急促的蜂鸣："这是……Glados的'星光地图'。"

你走近那张地图。节点有几十个，每个都标着矿区不同位置的代号。连线上的数字不是距离——是风险值。有些线很粗，表示安全；有些线细得像蛛丝，表示有猎杀者巡逻。

"他规划了一条路线。"你说，"从G-7到G-10，经过每一个节点恰好一次，然后回到起点。"

"为啥子要每个节点都走？"CC走过来，仰望着洞顶的水晶星空。

"因为Echo的碎片不只有一个。"你说，"Glados在找所有的碎片。每经过一个节点，他就记录一次信号强度——有些节点有碎片残留，有些没有。"

Echo的声音变得很轻："他在……他在收集我。"

"他在救你。"CC说。

你蹲下来，开始研究那张地图。要经过所有节点、每个只走一次、最后回到起点——这像是一个巨大的拼图游戏。但拼图的块数太多，暴力尝试的话，到你头发白了也试不完。

"可以用集合来记录。"你说，"每一个节点对应一个'记忆位'——去过就点亮，没去过就暗淡。整组'记忆位'合在一起，就是一个数字。我用这个数字来代表'已经去过哪些地方'，然后用一个表格记录下来：从这种状态出发，到达某个节点的最短风险值是多少。"

Echo："你在用数字的开关状态来压缩整个地图的遍历历史。"

"对。"你开始构建那个表格，"每一个'记忆状态'都只会被计算一次。一旦算出了从它到某个节点的最优路径，就永远不再重复计算。"

CC看着你一行一行写，她看不懂那些公式，但她看懂了你的眼神。那是猎手在管道迷宫里发现目标踪迹时的眼神——专注、敏锐、带着某种安静的兴奋。

屏幕上跳出了结果。一条由节点编号组成的路径，从头到尾的风险值总和。

Echo念出了那个数字："四十七。"

CC转头看她："四十七……？"

"我的型号。"Echo说，"Echo-47。Glados走过的这条路，总风险值恰好是47。"

空洞里安静了很长时间。洞顶的水晶轻轻摇晃，在岩壁上投下细碎的光斑，像一场无声的流星雨。

"他在用这种方式告诉我，"Echo说，"他记得。"

CC把地图小心地折叠起来——实际上是用终端扫描保存，因为全息地图没有实体——然后塞进背包："那我们就继续走。走完他没走完的路。"

题目描述

$n$ 个点的带权有向图，求从 0 出发经过每个点恰好一次回到 0 的最短路径。

输入格式

$n$。然后 $n \times n$ 矩阵 $w[i][j]$。

输出格式

最短 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

输出样例

19

提示

• 用一个数字代表'已经去过哪些地方'——每个节点对应一个开关位。
• 记录从每种状态到达每个节点的最优路径，避免重复计算。
• $n \le 20$。

你们离开空洞时，洞顶的水晶忽然同时暗了一秒，然后又重新亮起。Echo说这是Glados设置的感应机关——有人取走地图后，水晶会重新排列，形成新的星空图案，防止Zero追踪。

"他连后路都想好了。"你说。

"他一直都想好了。"CC的声音从前面传来，"只是没来得及走。"

矿道在前方继续延伸。Echo的终端显示，G-10井架还有两公里。但你们都知道，真正的距离不是用公里算的——是用剩下的锁的数量算的。

还有最后两道锁。