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

题目描述

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

注意：

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

输入描述

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

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

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

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

客户id1  客户id2  distance

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

规格：

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

输出描述

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

用例

输入	2 1 1 1000 2 1200 1 2 300
输出	2500
说明	路径1：快递员先把快递送到客户1中，接下来直接走客户1到客户2之间的直通路线，最后走投递站和客户2之间的路，回到投递站，距离为 1000 + 300 + 1200 = 2500 路径2：快递员先把快递送到客户1手中，接下来回到快递站，再出发把客户2的快递送过去，再回到快递站，距离为 1000 + 1000 + 1200 + 1200 = 4400 路径3：快递员先把快递送到客户2手中，接下来直接走客户2到客户1之间的直通线路，最后走投递站和客户1之间的路，回到投递站，距离为 1200 + 300 + 1000 = 2500 其他路径...... 所有路径中，最短路径距离为 2500

输入	5 1 5 1000 9 1200 17 300 132 700 500 2300 5 9 400
输出	9200
说明	在所有可行的路径中，最短路径长度为 1000 + 400 + 1200 + 300 + 300 + 700 + 700 + 2300 + 2300 = 9200

题目解析

下图中 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不是顺序的，因此这里需要将客