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から開始した場合、費用は他の2つよりも高くなります。

これを解決するには、次の手順に従います-

• 関数depth_search（）を定義します。これはノードを取ります、p
  • d1：=-infinity
  • d2：=-infinity
  • adj_list [node]のx、yのペアごとに、do
    • xがpと同じでない場合、
      • d1：=最大（d1、depth_search（x、node）+ y）
      • d1> d2の場合、
        • d2とd1の値を入れ替える
      • ti [node]：=ti [node] + ti [x]
      • 0
      • SUM：=SUM + y
  • d1> 0の場合、
    • MAX：=最大（MAX、d1 + d2）
  • d2> 0で、tj [node]がゼロ以外の場合、
    • MAX：=最大（MAX、d2）
  • tj [node]がゼロ以外の場合、
    • d2：=max（0、d2）
  • return d2

例

理解を深めるために、次の実装を見てみましょう-

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