Chương trình tìm đường đi tối thiểu để giao tất cả thư tín trong Python

Giả sử có n thành phố được kết nối bởi n-1 con đường. Mọi thành phố đều có thể đến được từ thành phố khác. Hệ thống bưu chính giao k thư mỗi ngày đến k thành phố khác nhau. Một nhân viên bưu chính phải giao tất cả thư tín. Ta cần tìm khoảng cách tối thiểu nhân viên phải đi để giao hết thư. Nhân viên có thể bắt đầu từ bất kỳ thành phố nào.

Ví dụ, với đầu vào như hình minh họa và các thành phố giao thư (delv) là 1, 2, 4, đầu ra sẽ là 4.

Nhân viên có thể bắt đầu từ 1, 2 hoặc 4. Nếu bắt đầu từ 1: đường đi 1→2→4, ngược lại từ 4: 4→2→1. Tổng chi phí = 1 + 3 = 4. Nếu bắt đầu từ 2 thì chi phí lớn hơn.

Giải pháp

Để giải quyết bài toán này, ta thực hiện các bước sau:

• Định nghĩa hàm depth_search(node, p):
  • d1 := -infinity, d2 := -infinity
  • Với mỗi cặp x, y trong adj_list[node]:
    • Nếu x != p:
      • d1 := max(d1, depth_search(x, node) + y)
      • Nếu d1 > d2: hoán đổi d1, d2
      • ti[node] := ti[node] + ti[x]
      • Nếu 0 < ti[x] < k: SUM := SUM + y
  • Nếu d1 > 0: MAX := max(MAX, d1 + d2)
  • Nếu d2 > 0 và tj[node] != 0: MAX := max(MAX, d2)
  • Nếu tj[node] != 0: d2 := max(0, d2)
  • Trả về d2
• k := kích thước delv
• adj_list := map mới
• ti, tj := danh sách kích thước (nodes + 5) khởi tạo 0
• Với mỗi i trong delv: ti[i] := 1, tj[i] := 1
• Với mỗi item trong roads:
  • x := item[0], y := item[1], c := item[2]
  • Thêm (y, c) vào adj_list[x] và (x, c) vào adj_list[y]
• SUM := 0, MAX := 0
• Gọi depth_search(1, 1)
• Trả về SUM * 2 - MAX

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

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)]))

Đầu vào

5, [1, 2, 4], [(1,2,1),(2,3,2),(2,4,3),(1,5,1)]

Đầu ra

4