資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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 := -無窮大
- 對於 adj_list[node] 中的每一對 x, y，執行以下操作：
- 如果 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)
- 返回 d2
- 如果 x 不等於 p，則
- k := delv 的大小
- adj_list := 一個新的對映
- ti := 一個新的列表，大小為 (nodes + 5)，初始化為 0
- tj := 一個新的列表，大小為 (nodes + 5)，初始化為 0
- 對於 delv 中的每個 i，執行以下操作：
- ti[i] := 1
- tj[i] := 1
- 對於 roads 中的每個專案，執行以下操作：
- x := item[0]
- y := item[1]
- c := item[2]
- 如果 adj_list 中不存在 x，則
- adj_list[x] := []
- 如果 adj_list 中不存在 y，則
- adj_list[y] := []
- 將 (y, c) 附加到 adj_list[x] 的末尾
- 將 (x, c) 附加到 adj_list[y] 的末尾
- SUM := 0
- MAX := 0
- depth_search(1, 1)
- 返回 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)]
輸出
4
更新於: 2021年10月6日
132 次瀏覽
廣告