快递员的烦恼 - 华为OD统一考试（C卷）

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()，动态规划的时间复杂度为O()，总体时间复杂度为O()。

空间复杂度

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

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]);
                }