โปรแกรมหาเส้นทางสั้นที่สุดส่งจดหมายทั้งหมดใน Python

สมมติว่ามี n เมืองเชื่อมต่อด้วย n-1 ถนน เมืองใดก็ตามสามารถไปถึงจากเมืองอื่นได้ ระบบไปรษณีย์ส่งจดหมาย k ฉบับต่อวัน จดหมายมีปลายทางเป็น k เมืองที่ต่างกัน พนักงานไปรษณีย์ต้องส่งจดหมายทั้งหมดทุกวัน เราต้องหาระยะทางขั้นต่ำที่พนักงานต้องเดินทางเพื่อส่งจดหมายทั้งหมด พนักงานสามารถเริ่มจากเมืองใดก็ได้

เช่น ถ้าอินพุตเป็นดังภาพ และจดหมายต้องส่งที่เมือง (delv) 1, 2, และ 4 ผลลัพธ์จะเป็น 4

พนักงานสามารถเริ่มส่งจากเมือง 1, 2, หรือ 4 ถ้าเริ่มที่เมือง 1 เส้นทางจะเป็น 1→2→4 ค่าใช้จ่ายรวม 1 + 3 = 4 ถ้าเริ่มจากเมือง 2 ค่าใช้จ่ายจะมากกว่า

วิธีแก้ปัญหา

กำหนดฟังก์ชัน depth_search() รับ node, p:
- d1 := -infinity, d2 := -infinity
- สำหรับแต่ละคู่ x, y ใน adj_list[node]:
  - ถ้า 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)
- return d2
k := ขนาดของ delv
adj_list := แมปใหม่
ti := รายการใหม่ขนาด (nodes + 5) เริ่มต้น 0
tj := รายการใหม่ขนาด (nodes + 5) เริ่มต้น 0
สำหรับแต่ละ i ใน delv: ti[i] := 1, tj[i] := 1
สำหรับแต่ละ item ใน roads: สร้าง adj_list ด้วย (y, c) และ (x, c)
SUM := 0, MAX := 0
depth_search(1, 1)
return 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)]

โปรแกรมหาเส้นทางสั้นที่สุดส่งจดหมายทั้งหมดใน Python

วิธีแก้ปัญหา

ตัวอย่าง

อินพุต

เอาต์พุต