题解

题目描述

小明计划到某网红旅游景区进行一次“特种兵”旅游。景区共有 $N$ 个景点，编号从 $1$ 到 $N$，编号为 $0$ 的点表示景区入口。给定一个 $(N+1) \times (N+1)$ 的矩阵 $G$，其中：

• $G[0][j]$ 表示从景区入口到景点 $j$ 的耗时。
• $G[j][0]$ 表示从景点 $j$ 到景区入口的耗时。
• $G[i][j]$ 表示从景点 $i$ 到景点 $j$ 的耗时。

题目内容

小明计划到某网红旅游景区来一次“特种兵”旅游，景区有 $N$ 个最点,请帮助小明规划一条游览路径，使得游览完所有景点花费的时间最短,以便于安排返程时间。

输入描述

第一行，景点数量 $N$ 。

接下来的 $N+1$ 行，每行 $N+1$ 个整数，以空格分隔，构成一个 $N+1*N+1$ 的矩阵。其中，坐标 $0$ 表示景区入口，$G[0] [j]$ 表示从景区入口到景区 $j$ 路程的耗时，$G[j] [0]$ 表示从景区 $j$ 到景区入口路程的耗时，$G [i] [j]$ 表示从景区 $i$ 到景点 $j$ 路程的耗时。

由于景区的道路不总是平坦的，景点间往返路程上花费的时间可能不同。如果 $i=j$，$G [i] [j] =0$ ；如果景点 $i$ 与景点 $j$ 之间没有直接相通的道路，则 $G [i] [j]=G [j] [i] = -1$；从景区入口，一定可以到达每一个景点(直达或者经过其它景点)。

• $1 <= N <= 15$

• 从景区入口出发，可以到达所有景点，要么是直达，要么是经过其它景点

• 在游览路径中，可以重复经过任一景点

输出描述

游览完所有景点在路途上花费的最短时间。

样例1

输入

2
0 2 3
1 0 5
2 2 0

输出

6

说明

如图所示， 游览路径: 景区入口>景点 $2$ ->景点 $1$ ->景区入口，耗时 $3+2+1=6$ 最少。

样例2

输入

3
0 1 2 -1
3 0 5 2
2 2 0 3
-1 2 4 0

输出

9

说明

如图所示，游览路径:景区入口->景点 $1$ ->景点 $3$ ->景点 $2$ ->景区入口，耗时 $1+2+4+2=9$ 最少。

样例3

输入

3
0 1 3 1
2 0 -1 -1
1 -1 0 4
1 -1 5 0

输出

9

说明

如图所示，游览路径:景区入口>景点 $1$ -> 景区入口 -> 景点 $2$ ->景区入口->景点 $3$ ->景区入口，耗时$1+2+3+1+1+1=9$ 最少。