OD统一考试（C卷）
分值： 200分
题解： Java / Python / C++
题目描述
快递公司每日早晨，给每位快递员推送需要淡到客户手中的快递以及路线信息，快递员自己又查找了一些客户与客户之间的路线距离信息，请你依据这些信息，给快递员设计一条最短路径，告诉他最短路径的距离。
-
不限制快递包裹送到客户手中的顺序，但必须保证都送到客户手中；
-
用例保证一定存在投递站到每位客户之间的路线，但不保证客户与客户之间有路线，客户位置及投递站均允许多次经过；
-
所有快递送完后，快递员需回到投递站；
输入描述
首行输入两个正整数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(n3)，动态规划的时间复杂度为O(2n * n2)，总体时间复杂度为O(n3 + 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; // 自己到自己的距离为0
for (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 inf
n, 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] = distance
idx_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 # 自己到自己的距离为0
for 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; // 自己到自己的距离为0
for (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加群”
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
