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

题目描述

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

注意：

• 不限制快递包裹送到客户手中的顺序，但必须保证都送到客户手中
• 用例保证一定存在投递站到每位客户之间的路线，但不保证客户与客户之间有路线，客户位置及投递站均允许多次经过
• 所有快递送完后，快递员需回到投递站

输入描述

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

接下来 n 行，输入快递公司发布的客户快递信息，格式为：

客户id  投递站到客户之间的距离distance

再接下俩的 m 行，是快递员自行查找的客户与客户之间的距离信息，格式为

客户id1  客户id2  distance

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

规格：

• 0 < n ≤ 10
• 0 ≤ m ≤ 10
• 0 < 客户id ≤ 1000
• 0 < distance ≤ 10000

输出描述

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

用例

题目解析

下图中 0节点 代表快递站。

用例1图示

用例2图示

import Foundation

func ODTest_2_38() {
    print("输入描述")
    print("首行输入两个正整数n、m")
    let nm = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 }
    let n = nm[0]
    let m = nm[1]

    // floyd算法需要基于dist和path矩阵求解
    // dist[i][j] 用于记录点 i->j 的最短距离，初始时等价于邻接矩阵
    var dist = Array(repeating: Array(repeating: 0, count: n + 1), count: n + 1)
    // path[i][j] 用于记录点 i->j 最短距离情况下需要经过的中转点，初始时默认任意两点间无中转点，即默认path[i][j] = -1
    var path = Array(repeating: Array(repeating: -1, count: n + 1), count: n + 1)
    for i in 0 ... n {
        for j in 0 ... n {
            // 初始时默认i,j不相连，即i,j之间距离无穷大
            if i != j {
                dist[i][j] = Int.max
            }
        }
    }
    print("接下来 n 行，输入快递公司发布的客户快递信息，格式为：")
    // 由于本题的客户id不是顺序的，因此这里需要将客户id离散化处理
    var map: [Int: Int] = [:]
    for i in 1 ... n {
        let Id_Dis = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 }
        if Id_Dis.count == 2 {
            // 离散化处理
            map[Id_Dis[0]] = i
            // 投递站到客户之间的距离distance
            dist[0][i] = Id_Dis[1]
            dist[i][0] = Id_Dis[1]
        }
    }

    print("再接下俩的 m 行，是快递员自行查找的客户与客户之间的距离信息，格式为")
    print("在每行数据中，数据与数据之间均以单个空格分隔")
    for _ in 1 ... m {
        let Dis = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 }
        if Dis.count == 3, let i1 = map[Dis[0]], let i2 = map[Dis[1]] {
            // 客户与客户之间的距离信息
            dist[i1][i2] = Dis[2]
            dist[i2][i1] = Dis[2]
        }
    }
    // floyd算法:用于解决全源最短路径问题
    floyd()

    // ans记录经过所有点后回到出发点的最短距离
    var ans = Int.max
    // 全排列模拟经过所有点的路径
    var boolean = Array(repeating: false, count: n + 1)
    dfs(0, 0, &boolean, 0)
    print("输出描述")
    print("最短路径距离，如无法找到，请输出-1")
    print("\(ans)")

    /**
     * 找一条经过所有点的最短路径，我们可以求解所有点形成的全排列，每一个全排列都对应一条经过所有点的路径，只是经过点的先后顺序不同 //
     * 求某个全排列过程中，可以通过dist数组，累计上一个点i到下一个点j的最短路径dist[i][j]
     *
     * @param pre 上一个点, 初始为0，表示从快递站出发
     * @param sum 当前全排列路径累计的路径权重
     * @param used 全排列used数组，用于标记哪些点已使用过
     * @param level 用于记录排列的长度
     */
    func dfs(_ pre: Int, _ sum: Int, _ used: inout [Bool], _ level: Int) {
        if level == n {
            // 此时pre是最后一个客户所在点，送完最后一个客户后，快递员需要回到快递站，因此最终累计路径权重为 sum + dist[pre][0]
            // 我们保留最小权重路径
            ans = min(ans, sum + dist[pre][0])
            return
        }
        for i in 1 ... n {
            if used[i] { continue }
            used[i] = true
            dfs(i, sum + dist[pre][i], &used, level + 1)
            used[i] = false
        }
    }

    //  floyd算法
    //  是一种用于解决图中所有节点对之间最短路径的动态规划算法
    //  原理：通过动态规划的方式，逐步考虑每个顶点作为中间点，更新所有顶点对之间的最短路径。
    //  时间复杂度：O(V^3)，其中 V 是顶点数。
    func floyd() {
        for k in 0 ... n {
            for i in 0 ... n {
                for j in 0 ... n {
                    // newDist是经过k后，i->j的距离
                    let newDist = dist[i][k] + dist[k][j]
                    // 如果newDist是i->j的更短路径
                    if newDist < dist[i][j] {
                        // 则更新i->j的最短距离
                        dist[i][j] = newDist
                        // 且此更短距离需要经过k, path[i][j]即记录 i->j 最短距离下需要经过点 k
                        path[i][j] = k
                    }
                }
            }
        }
    }
}