Description

小明要去旅游，一共有 n 个城市要访问，这些城市之间都有公路相连（不一定对称，也不一定满足三角形不等式）。

他计划从城市 1 出发，经过每个城市恰好一次，最后回到城市 1，形成一条“环游路线”。

给定任意两个城市之间的路程，求小明完成这次旅行所需的最短总路程。 如果不存在这样的环游路线，则输出 -1。

提示：n 的规模比较小，可以考虑使用深度优先搜索枚举所有可能路线，并配合剪枝或状态压缩优化。

Input Format

• 第一行一个整数 n（2 ≤ n ≤ 15），表示城市数量，城市编号为 1…n。
• 接下来有 n 行，每行 n 个整数，构成一个矩阵 dist：
  • 第 i 行第 j 列的整数表示从城市 i 到城市 j 的路程；
  • 若 dist[i][j] = -1，表示 i 到 j 没有直接公路；
  • 保证 dist[i][i] = 0。

Output Format

• 输出一个整数，表示从城市 1 出发，访问每个城市恰好一次并回到城市 1 的 最短总路程；
• 若不存在这样的路线，输出 -1。

4
0 10 15 20
10 0 35 25
15 35 0 30
20 25 30 0

80

解释：
一种最优路线为 1 -> 2 -> 4 -> 3 -> 1，总路程为 10 + 25 + 30 + 15 = 80。

3
0  5 -1
5  0  7
-1 7  0

-1

解释：
由于 1 和 3 之间没有道路，无法找到一条经过 1,2,3 每个城市一次并回到 1 的环游路线。

Source

DFS 深度优先搜索（旅行中的最短路线）