HTML CSS JAVASCRIPT JQUERY AI PHP SQL EXCEL LINUX C# C++ C PYTHON JAVA 教程库 参考手册 技术文章 测验 练习 HOWTO FAQ

用 Python 编写程序，找出投递所有信件的最短路径

pythonserver side programmingprogramming更新于 2025/12/2 17:48:17

假设有 n 个城市，它们与 n -1 条道路相连。可以从任何其他城市访问一个城市。现在，城市的邮政系统每天投递 k 封信件。信件的目的地可以是 k 个不同城市中的任何一个。邮政工作人员每天必须将所有信件投递到他们的地址。我们必须找出工作人员投递所有信件所需行驶的最短距离。工作人员可以从任何给定城市出发。

因此，如果输入如下

并且信件必须在城市 (delv) 1、2 和 4 中投递；那么输出将是 4。

工人可以从城市 1、2 或 4 开始送货。如果工人从城市 1 开始，那么路径将是 1->2->4，如果是城市 4，则反之亦然；4->2->1。总成本将是 1 + 3 = 4。如果他从城市 2 出发，成本将大于其他两个。

为了解决这个问题，我们将遵循以下步骤 −

  • 定义一个函数depth_search()。这将获取节点 p
    • d1 := -infinity
    • d2 := -infinity
    • 对于 adj_list[node] 中的每一对 x、y，执行
      • 如果 x 与 p 不同，则
        • d1 := (d1,depth_search(x,node)+y) 的最大值
        • 如果 d1 > d2，则
          • 交换 d2 和 d1 的值
        • ti[node] := ti[node] + ti[x]
        • 如果 0 < ti[x] < k，则
          • SUM := SUM + y
      • 如果 d1 > 0，则
        • MAX := (MAX, d1 + d2) 的最大值
      • 如果 d2 > 0 且 tj[node] 非零，则
        • MAX := (MAX, d2) 的最大值
      • 如果 tj[node] 非零，则
        • d2 := max(0, d2)
      • 返回 d2
  • k := delv 的大小
  • adj_list := 一个新的映射
  • ti := 一个新的大小为 (nodes + 5) 的列表，初始化为 0
  • tj := 一个新的大小为 (nodes + 5) 的列表，初始化为 0
  • 对于 delv 中的每个 i，执行
    • ti[i] := 1
    • tj[i] := 1
  • 对于 roads 中的每个项目，执行
    • x := item[0]
    • y := item[1]
    • c := item[2]
    • 如果 x 不在 adj_list 中，则
      • adj_list[x] := []
    • 如果 y 不存在于 adj_list 中，则
      • adj_list[y] := []
    • 将 (y, c) 附加到 adj_list[x] 的末尾
    • 将 (x, c) 附加到 adj_list[y] 的末尾
  • SUM := 0
  • MAX := 0
  • depth_search(1, 1)
  • 返回 SUM * 2 - MAX

示例

让我们看看下面的实现以便更好地理解 −

import sys
from math import inf as INF
sys.setrecursionlimit(10**5 + 5)

def depth_search(node, p):
    global SUM, MAX
    d1 = -INF
    d2 = -INF

    for x, y in adj_list[node]:
        if x != p:
            d1 = max(d1, depth_search(x, node) + y)
            if d1 > d2:
                d1, d2 = d2, d1

            ti[node] += ti[x]
            if 0 < ti[x] < k:
                SUM += y

    if d1 > 0: MAX = max(MAX, d1 + d2)
    if d2 > 0 and tj[node]: MAX = max(MAX, d2)
    if tj[node]: d2 = max(0, d2)

    return d2

def solve(nodes, delv, roads):
    global k, ti, tj, adj_list, SUM, MAX
    k = len(delv)
    adj_list = {}
    ti = [0] * (nodes + 5)
    tj = [0] * (nodes + 5)

    for i in delv:
        ti[i] = tj[i] = 1

    for item in roads:
        x, y, c = map(int, item)
        if x not in adj_list: adj_list[x] = []
        if y not in adj_list: adj_list[y] = []

        adj_list[x].append([y, c])
        adj_list[y].append([x, c])

    SUM = 0
    MAX = 0
    depth_search(1,1)
    return SUM * 2 - MAX

print(solve(5, [1, 2, 4], [(1,2,1),(2,3,2),(2,4,3),(1,5,1)]))

输入

5, [1, 2, 4], [(1,2,1),(2,3,2),(2,4,3),(1,5,1)]

输出

4

相关文章

有用资源

打印 下一节:用 Python 编写程序，找出图中所有顶点的最小成本之和 ❯❮ 上一节:用 Python 编写程序，找出给定图中特殊类型的子图