โปรแกรมหาเส้นทางขั้นต่ำในการส่งตัวอักษรทั้งหมดใน 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 :=-อินฟินิตี้
  • สำหรับแต่ละคู่ x, y ใน adj_list[node], do
    • ถ้า x ไม่เหมือนกับ p แล้ว
      • d1 :=สูงสุดของ (d1, depth_search(x, โหนด) + 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[โหนด] ไม่ใช่ศูนย์ ดังนั้น
    • 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