最新华为OD机试真题-快递员的烦恼(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

最新华为OD机试D卷目录，全、新、准，题目覆盖率达 95% 以上，支持题目在线评测

最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users

📎在线评测链接

快递员的烦恼(200分)

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🎀 快递员的烦恼

问题描述

K 小姐是一名快递员，每天早上她都会收到公司发来的客户快递信息和路线信息。同时，K 小姐也会自行查找一些客户与客户之间的路线距离信息。现在，请你帮助 K 小姐设计一条最短路径，告诉她最短路径的距离。

需要注意以下几点:

1. 快递包裹送到客户手中的顺序不限，但必须保证都送到客户手中。
2. 一定存在投递站到每位客户之间的路线，但不保证客户与客户之间有路线。客户位置及投递站均允许多次经过。
3. 所有快递送完后，K 小姐需要回到投递站。

输入格式

第一行输入两个正整数 。

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

再接下来的 行，是 K 小姐自行查找的客户与客户之间的距离信息，格式为: 客户 1 id 客户 2 id distance。

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

输出格式

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

样例输入 1

2 1
1 1000
2 1200
1 2 300

样例输出 1

2500

样例解释 1

路径: K 小姐先把快递送到客户 1 手中，接下来直接走客户 1 到客户 2 之间的直通线路，最后走投递站和客户 2 之间的路，回到投递站，距离为 1000 + 300 + 1200 = 2500。

样例输入 2

5 1
5 1000
9 1200
17 300
132 700
500 2300
5 9 400

样例输出 2

9200

数据范围

题解

在这个问题中，我们需要找到一条最短路径，使得快递员能够将所有快递包裹送到客户手中，并最终回到投递站。我们可以将这个问题建模为一个加权无向图的最短路径问题。

首先，我们需要构建一个加权无向图。图中的节点包括投递站和所有客户。对于每个客户，我们将其与投递站之间的距离作为边的权重。同时，对于任意两个客户之间存在的路线，我们也将其作为边加入图中。

接下来，我们可以使用动态规划的方法来求解最短路径。我们定义 表示已经访问了状态 中的所有客户，并且当前位于节点 时的最短路径长度。我们可以通过枚举所有可能的状态转移来更新 数组。

最终，我们需要找到 的值，即访问了所有客户并回到投递站的最短路径长度。如果无法找到这样的路径，我们输出 -1。

参考代码

• Python

n, m = list(map(int, input().split()))
dist = [[-1] * (n + 1) for _ in range(n + 1)]
dct, ids = {}, 1
for _ in range(n):
    p, dst = list(map(int, input().split()))
    if p not in dct:
        dct[p] = ids
        ids += 1
    dist[0][dct[p]] = dst
    dist[dct[p]][0] = dst

for _ in range(m):
    f, t, dst = list(map(int, input().split()))
    dist[dct[f]][dct[t]] = dst
    dist[dct[t]][dct[f]] = dst

for k in range(n + 1):
    for i in range(n + 1):
        for j in range(n + 1):
            if dist[i][k] != -1 and dist[k][j] != -1 and (dist[i][j] == -1 or dist[i][k] + dist[k][j] < dist[i][j]):
                dist[i][j] = dist[i][k] + dist[k][j]

dp = [[10 ** 10] * (n + 1) for _ in range(1 << (n + 1))]
dp[1][0] = 0
for i in range(1, 1 << (n + 1)):
    for j in range(n + 1):
        if i & (1 << j) == 0:
            continue
        for k in range(n + 1):
            dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + dist[j][k])
ans = dp[(1 << (n + 1)) - 1][0]
print(ans if ans != 10 ** 10 else -1)

• Java

import java.util.*;

public class Main {
    static final int INF = (int) 1e9;
    static int n, m;
    static int[][] dist;
    static Map<Integer, Integer> dct = new HashMap<>();
    stat