题目内容

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

输入描述

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

题解

题目描述

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

• $G[0][j]$ 表示从景区入口到景点 $j$ 的耗时。
• $G[j][0]$ 表示从景点 $j$ 到景区入口的耗时。
• $G[i][j]$ 表示从景点 $i$ 到景点 $j$ 的耗时。
• 如果 $G[i][j] = -1$，表示景点 $i$ 与景点 $j$ 之间没有直接通路。