假设有 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 开始,成本将大于其他两个。
让我们看看以下实现以更好地理解 -
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