Python程序以找到递送所有信件的最短路径

假设有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()。这将接受node、p两个参数
  • d1 := -无穷大
  • d2 := -无穷大
  • 对于邻接列表中的每一对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
• 对于每个i在delv中，执行以下操作：
  • ti [i]：= 1
  • tj [i]：= 1
• 对于道路中的每个项目，执行以下操作：
  • x：= item [0]
  • y：= item [1]
  • c：= item [2]
  • 如果x不在adj_list中，则
    • adj_list [x]：= []
  • 如果y不在adj_list中，则
    • adj_list [y]：= []
    • 在adj_list [x]的末尾添加（y，c）
    • 在adj_list [y]的末尾添加（x，c）
  • 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