pta团体程序设计天梯赛l2014

### PTA 团体程序设计天梯赛 L2-014 题目及解析 #### 题目描述 在一个由 N 个城市组成的国家里，城市之间通过双向道路连接。每条道路上都有一个通行时间。现在有一个紧急情况发生，需要从某个特定的城市出发前往另一个指定的城市，在这个过程中要经过一些检查站来获取必要的物资补给。每个城市都设有一个检查站，其中含有不同数量的物资包。 任务目标是从起点城市到达终点城市的过程中： 1. 计算能够获得的最大物资包总数； 2. 如果有多条路径可以获得相同数量的最大物资包，则选择总行驶时间最短的一条路径；如果仍然存在多条最优路径，则输出任意一条即可。 输入格式如下： - 第一行包含两个整数N (2 ≤ N ≤ 500)，表示城市的数目，以及 M 表示道路的数量。 - 接下来的一行中有 N 个正整数 Wi, 分别代表第 i 座城市中的物资包数量(0≤Wi<10^9)。 - 后面还有 M 行数据，每一行有三个整数 Ci,Cj,Tij 描述了一条连接两座城巿Ci 和 Cj 的无向边及其所需的时间 Tij (1 ≤ Ti,j < 10^9)。 - 最后一行有两个不同的整数 S,D 分别指明起始位置S和目的地D。(1 ≤ S,D ≤ N) 对于这个问题，可以采用带权图上的广度优先搜索(BFS)[^1] 或者基于动态规划的方法解决此问题。具体来说： 为了实现上述功能，可以通过以下 Python 实现方案来进行处理: ```python from collections import defaultdict, deque import heapq def max_rescue_bags(N, roads, bags, start, end): graph = defaultdict(list) for u, v, w in roads: graph[u].append((v, w)) graph[v].append((u, w)) # Priority queue to store the current state as a tuple of (-bags_count, time_cost, city_id) pq = [(-bags[start], 0, start)] visited = {start: (bags[start], 0)} while pq: cur_bags, cost, node = heapq.heappop(pq) if node == end: return -cur_bags for neighbor, weight in graph[node]: next_bags = -cur_bags + bags[neighbor] next_cost = cost + weight if neighbor not in visited or visited[neighbor][0] < next_bags or \ (visited[neighbor][0] == next_bags and visited[neighbor][1] > next_cost): visited[neighbor] = (next_bags, next_cost) heapq.heappush(pq, (-next_bags, next_cost, neighbor)) return "No path found" # Example usage if __name__ == "__main__": n = 5 m = 6 wi = [10, 8, 7, 1, 3] ci_cj_tij = [(1, 2, 1), (1, 3, 4), (2, 4, 2), (3, 4, 3), (2, 5, 2), (3, 5, 3)] s = 1 d = 5 result = max_rescue_bags(n, ci_cj_tij, wi, s, d) print(f"The maximum number of rescue bags that can be collected is {result}.") ```