1000ms

Difficulty: 7

所属公司 : 华为

时间 :2022年9月23日-国内-非AI方向

算法与标签>动态规划

会员或题库专享

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

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

会员专享

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

购买题库开通会员

DFS暴力解法

这道题的正解是 $Floyd$ 最短路加 $状态压缩DP$ ，但是我们用朴素解法 $DFS$ 枚举游览顺序也能在考试时拿到一定的分数。

题意：从城市 $0$ 出发，逛完全部 $n$ 个城市后回到 $0$ ，城市之间费用由邻接矩阵给出，允许重复经过城市，求最低总费用。

朴素思路：

先用 $Floyd$ 把邻接矩阵变成任意两点最短路 $d[u][v]$ （允许途经其他城市）。