파이썬에서 모든 문자를 전달하기 위한 최소 경로를 찾는 프로그램

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[노드]의 각 쌍 x, y에 대해 수행
    • x가 p와 같지 않으면
      • d1 :=(d1, depth_search(x, node) + y)의 최대값
      • d1> d2이면
        • d2와 d1의 값 바꾸기
      • ti[노드] :=ti[노드] + ti[x]
      • 0
      • 합 :=합 + y
  • d1> 0이면
    • MAX :=(MAX, d1 + d2)의 최대값
  • d2> 0이고 tj[node]가 0이 아니면
    • MAX :=최대(MAX, d2)
  • tj[노드]가 0이 아니면
    • d2 :=최대(0, d2)
  • 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