1000ms

Difficulty: 8

所属公司 : 华为

时间 :2024年11月20日-留学生-非AI方向

算法与标签>动态规划

会员或题库专享

请先，开通会员或购买题库华为校招机考题库，可解锁完整内容。

购买华为校招机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（华为校招机考题库），可解锁完整内容。

购买题库开通会员

题解

题目描述

小明计划到某网红旅游景区进行一次“特种兵”旅游。景区共有 $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$ 。