快递员的烦恼 - 华为OD统一考试

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

题目描述

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

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

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

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

输入描述

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

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

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

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

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

输出描述

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

示例1

输入：
2 1
1 1000
2 1200
1 2 300输出：
2500说明：
快递员先把快递送到客户1手中，接下来直接走客户1到客户2之间的直通线路，最后走投递站和客户2之间的路，回到投递站，距离为1000+300+1200= 2500

示例2

输入：
5 1
5 1000
9 1200
17 300
132 700
500 2300
5 9 400输出：
9200

题解

这道题目属于图论中的最短路径问题。题目要求找到一条路径，使得快递员从投递站出发，依次经过所有客户，最后回到投递站，使得路径的总距离最短。

首先，我们需要构建一个图，图中的节点表示投递站和所有客户，边表示它们之间的距离。由于题目中给出了客户之间的距离信息，我们可以使用 Floyd 算法来计算任意两点之间的最短距离。

接下来，我们使用动态规划来求解最短路径。定义dp[state][last]表示当前情况下已经投递的客户集合为state，上一次投递的客户为last时，已经走过的最短距离。状态转移方程为：

dp[state | (1 << last)][last] = min(dp[state | (1 << last)][last], dp[state][i] + dist[i][last])

其中，state为二进制表示的已经投递的客户集合，state | (1 << last)表示将state中last位置设置为1，last 表示上一次投递的状态。dist[i][last]表示投递的客户的最短距离。

时间复杂度

Floyd-Warshall算法的时间复杂度为O(n^{3)，动态规划的时间复杂度为O(2}n * n^{2)，总体时间复杂度为O(n}3 + 2^n * n^2)。

空间复杂度

空间复杂度主要由存储距离矩阵和动态规划数组决定，为O(n^2 + 2^n * n)。

Java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
/*** @author code5bug*/
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(), m = scanner.nextInt();int[][] dist = new int[n + 1][n + 1];for (int i = 0; i < dist.length; i++) Arrays.fill(dist[i], Integer.MAX_VALUE);// 客户id 和索引下标的对照表Map<Integer, Integer> idxMap = new HashMap<>();// 初始化客户id 到 投递站(0) 之间的距离for (int idx = 1; idx <= n; idx++) {int cid = scanner.nextInt();int distance = scanner.nextInt();dist[0][idx] = dist[idx][0] = distance;idxMap.put(cid, idx);}// 初始化客户与客户之间的距离for (int i = 0; i < m; i++) {int cid1 = scanner.nextInt(), cid2 = scanner.nextInt(), distance = scanner.nextInt();int idx1 = idxMap.get(cid1), idx2 = idxMap.get(cid2);dist[idx1][idx2] = dist[idx2][idx1] = distance;}// Floyd-Warshall算法 求出所有点之间的最短距离 时间复杂度为O(n^3)for (int k = 0; k <= n; k++) {dist[k][k] = 0;  // 自己到自己的距离为0for (int i = 0; i <= n; i++) {for (int j = 0; j <= n; j++) {dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);}}}// dp[state][last] 当前情况走过的最短距离// state 表示已经投递的客户 （指定二进制位为1表示已经投递），last表示上一次投递的客户int[][] dp = new int[1 << (n + 1)][n + 1];for (int i = 0; i < (1 << (n + 1)); i++) Arrays.fill(dp[i], Integer.MAX_VALUE);dp[1][0] = 0;  // 初始状态，在投递站for (int state = 0; state < (1 << (n + 1)); state++) {for (int i = 0; i <= n; i++) {if ((state >> i & 1) == 1 && dp[state][i] != Integer.MAX_VALUE) {    // 如果 i 已经投递 且 可达for (int last = 0; last <= n; last++) {dp[state | (1 << last)][last] = Math.min(dp[state | (1 << last)][last], dp[state][i] + dist[i][last]);}}}}System.out.println(dp[(1 << (n + 1)) - 1][0]);}
}

Python

from math import infn, m = map(int, input().split())
dist = [[inf] * (n + 1) for _ in range(n + 1)]# 客户id 和索引下标的对照表
idx_map = {}# 初始化客户id  到 投递站(0) 之间的距离
for idx in range(1, n + 1):cid, distance = map(int, input().split())dist[0][idx] = dist[idx][0] = distanceidx_map[cid] = idx# 初始化客户与客户之间的距离
for _ in range(m):cid1, cid2, distance = map(int, input().split())idx1, idx2 = idx_map[cid1], idx_map[cid2]dist[idx1][idx2] = dist[idx2][idx1] = distance# Floyd-Warshall算法 求出所有点之间的最短距离  时间复杂度为O(n^3)
for k in range(n + 1):dist[k][k] = 0  # 自己到自己的距离为0for i in range(n + 1):for j in range(n + 1):dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])f = [[inf] * (n + 1) for _ in range(1 << (n + 1))]
f[1][0] = 0# dp[state][last] 当前情况走过的最短距离
# state 表示已经投递的客户 （指定二进制位为1表示已范围），last表示上一次投递的客户
dp = [[inf] * (n + 1) for _ in range(1 << (n + 1))]
dp[1][0] = 0  # 初始状态，在投递站for state in range(1 << (n + 1)):for i in range(n + 1):if (state >> i) & 1 and dp[state][i] != inf:    # 如果 i 已经投递 且 可达for last in range(n + 1):dp[state | (1 << last)][last] = min(dp[state | (1 << last)][last], dp[state][i] + dist[i][last])print(dp[(1 << (n + 1)) - 1][0])

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <climits>using namespace std;int main() {int n, m;cin >> n >> m;vector<vector<int>> dist(n + 1, vector<int>(n + 1, INT_MAX));// 客户id 和索引下标的对照表unordered_map<int, int> idxMap;// 初始化客户id 到 投递站(0) 之间的距离for (int idx = 1; idx <= n; idx++) {int cid, distance;cin >> cid >> distance;dist[0][idx] = dist[idx][0] = distance;idxMap[cid] = idx;}// 初始化客户与客户之间的距离for (int i = 0; i < m; i++) {int cid1, cid2, distance;cin >> cid1 >> cid2 >> distance;int idx1 = idxMap[cid1], idx2 = idxMap[cid2];dist[idx1][idx2] = dist[idx2][idx1] = distance;}// Floyd-Warshall算法 求出所有点之间的最短距离 时间复杂度为O(n^3)for (int k = 0; k <= n; k++) {dist[k][k] = 0;  // 自己到自己的距离为0for (int i = 0; i <= n; i++) {for (int j = 0; j <= n; j++) {dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);}}}// dp[state][last] 当前情况走过的最短距离// state 表示已经投递的客户 （指定二进制位为1表示已经投递），last表示上一次投递的客户vector<vector<int>> dp(1 << (n + 1), vector<int>(n + 1, INT_MAX));dp[1][0] = 0;  // 初始状态，在投递站for (int state = 0; state < (1 << (n + 1)); state++) {for (int i = 0; i <= n; i++) {if ((state >> i & 1) == 1 && dp[state][i] != INT_MAX) {    // 如果 i 已经投递 且 可达for (int last = 0; last <= n; last++) {dp[state | (1 << last)][last] = min(dp[state | (1 << last)][last], dp[state][i] + dist[i][last]);}}}}cout << dp[(1 << (n + 1)) - 1][0] << endl;return 0;
}

相关练习题

题号	题目	难易
LeetCode 2976	2976. 转换字符串的最小成本 I	中等

‍❤️‍华为OD机试面试交流群（每日真题分享）： 加V时备注“华为od加群”

🙏整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏