数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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() 。它将接收节点和 p 作为参数。
- d1 := -无穷大
- d2 := -无穷大
- 对于 adj_list[node] 中的每一对 x, y，执行以下操作：
- 如果 x 不等于 p，则
- d1 := max(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(MAX, d1 + d2)
- 如果 d2 > 0 且 tj[node] 不为零，则
- MAX := max(MAX, d2)
- 如果 tj[node] 不为零，则
- d2 := max(0, d2)
- 返回 d2
- 如果 x 不等于 p，则
- 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]
- 如果 adj_list 中不存在 x，则
- adj_list[x] := []
- 如果 adj_list 中不存在 y，则
- 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
更新于: 2021年10月6日
132 次浏览
广告