作為一個城市的應急救援隊伍的負責人，你有一張特殊的全國地圖。在地圖上顯示有多個分散的城市和一些連接城市的快速道路。每個城市的救援隊數量和每一條連接兩個城市的快速道路長度都標在地圖上。當其他城市有緊急求助電話給你的時候，你的任務是帶領你的救援隊盡快趕往事發地，同時，一路上召集盡可能多的救援隊。
輸入格式:
輸入第一行給出4個正整數N、M、S、D，其中N（2≤N≤500）是城市的個數，順便假設城市的編號為0 ~?(N?1)；M是快速道路的條數；S是出發地的城市編號；D是目的地的城市編號。
第二行給出N個正整數，其中第i個數是第i個城市的救援隊的數目，數字間以空格分隔。隨后的M行中，每行給出一條快速道路的信息，分別是：城市1、城市2、快速道路的長度，中間用空格分開，數字均為整數且不超過500。輸入保證救援可行且最優解唯一。
輸出格式:
第一行輸出最短路徑的條數和能夠召集的最多的救援隊數量。第二行輸出從S到D的路徑中經過的城市編號。數字間以空格分隔，輸出結尾不能有多余空格。
輸入樣例:
4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2
輸出樣例:
2 60
0 1 3分析：
- 首先，代碼從標準輸入讀取節點數 n，邊數 m，源點 s 和終點 d。接著，讀取每個節點的幫助值，并建立節點和其對應鄰居的邊（這里，邊是有向的，每個邊都連接兩個節點，并有一個相關的權重）。
- 然后，初始化一個距離數組 dist，用于存儲從源點 s 到每個節點的最短距離。同時，初始化兩個累計數組 total 和 sum_help，用于存儲從源點 s 到每個節點的所有節點的幫助值的總和。還初始化一個 parent 數組，用于存儲最短路徑上的節點。
- 使用堆（優先隊列）q 存儲待處理的節點。將源點 s 添加到堆中，并設置其距離為 0，總幫助值為 1，累計幫助值為其自身的幫助值。
- 然后，進入一個 while 循環，不斷地從堆中取出距離最小的節點，并更新其鄰居的距離和累計幫助值。如果鄰居的距離更新，那么就將其添加到堆中。
- 當堆為空時，結束循環。此時，dist 和 total 數組中存儲的值就是從源點 s 到每個節點的最短距離和累計幫助值。
- 最后，通過回溯 parent 數組，找出從源點 s 到終點 d 的最短路徑，并打印出來。同時，打印出終點的累計幫助值。
Python版本：
import heapq
import sysn, m, s, d = map(int, sys.stdin.readline().split())
help_val = list(map(int, sys.stdin.readline().split()))
edge = [[] for _ in range(n)]
for _ in range(m):x, y, z = map(int, sys.stdin.readline().split())edge[x].append((y, z))edge[y].append((x, z))dist = [float("inf") for _ in range(n)]
total = [0 for _ in range(n)]
sum_help = [0 for _ in range(n)]
p = [-1 for _ in range(n)]
dist[s] = 0
total[s] = 1
sum_help[s] = help_val[s]
q = []
heapq.heappush(q, (0, s))while q:tmp = heapq.heappop(q)x = tmp[1]if dist[x] < tmp[0]:continuefor i in edge[x]:if dist[i[0]] > dist[x] + i[1]:dist[i[0]] = dist[x] + i[1]total[i[0]] = total[x]sum_help[i[0]] = sum_help[x] + help_val[i[0]]p[i[0]] = xheapq.heappush(q, (dist[i[0]], i[0]))else:if dist[i[0]] == dist[x] + i[1]:total[i[0]] += total[x]sum_help_tmp = sum_help[x] + help_val[i[0]]if sum_help_tmp > sum_help[i[0]]:sum_help[i[0]] = sum_help_tmpp[i[0]] = xpath = []
x = d
while x != -1:path.append(str(x))x = p[x]
print(total[d], sum_help[d])
print(" ".join(path[::-1]))
總結：
?
這段代碼的主要創新點在于同時求解最短路徑和累計幫助值。這在一些實際的網絡優化問題中是非常有用的。例如，在緊急救援中，我們需要找出一條最短的路線，同時還要考慮沿途各個節點的資源（如食物、水等）的總量。
)
