华为OD机试 - 快递员的烦恼 - 动态规划（Java 2024 D卷 200分）_快递员的烦恼 华为机考

一、题目描述

快递公司每日早晨，给每位快递员推送需要淡到客户手中的快递以及路线信息，快递员自己又查找了一些客户与客户之间的路线距离信息，请你依据这些信息，给快递员设计一条最短路径，告诉他最短路径的距离。

不限制快递包裹送到客户手中的顺序，但必须保证都送到客户手中；

用例保证一定存在投递站到每位客户之间的路线，但不保证客户与客户之间有路线，客户位置及投递站均允许多次经过；

所有快递送完后，快递员需回到投递站；

二、输入描述

首行输入两个正整数n、m.

接下来n行，输入快递公司发布的客户快递信息，格式为：客户id 投递站到客户之间的距离distance

再接下来的m行，是快递员自行查找的客户与客户之间的距离信息，格式为：客户1id 客户2id distance

在每行数据中，数据与数据之间均以单个空格分割规格:

0 <=n <= 10 0 <= m <= 10 0 < 客户id <= 1000 0 < distance <= 10000

三、输出描述

最短路径距离，如无法找到，请输出-1

四、解题思路

可以利用图的遍历方法，特别是基于图的最短路径问题。这个问题实际上是一个变种的旅行销售员问题（TSP），需要找到一个最短的路径，让快递员从投递站出发，经过所有客户位置至少一次，然后返回投递站。我们可以通过以下步骤来解决这个问题&#x