本文共 2122 字，大约阅读时间需要 7 分钟。
为了解决这个问题，我们需要计算《三国志》中小白能得到的最大财宝数量。小白需要派出武将攻占其他城池，每走一公里消耗一石粮食。我们需要找到从0号城池出发，到其他各城池的最短路径，然后根据粮食限制，选择能到达的最多财宝的城池。
问题转化为图问题：城池可以看作图中的节点，道路是边，道路的权重是距离（石粮食）。我们需要计算从0号城池到其他各城池的最短路径。
使用Dijkstra算法：计算从0号城池到所有其他城池的最短距离。因为道路是双向的，所以需要考虑正向和反向的道路。
收集可达的城池：根据最短距离，收集所有粮食不超过限制的城池，并记录它们的最短距离和财宝数量。
0-1背包问题：在有限的粮食限制下，选择能到达的城池，使得总财宝最大。这是一个典型的0-1背包问题，可以通过动态规划解决。
import sysimport heapqdef main(): input = sys.stdin.read().split() ptr = 0 T = int(input[ptr]) ptr += 1 for _ in range(T): S = int(input[ptr]) N = int(input[ptr+1]) M = int(input[ptr+2]) ptr +=3 # Read M roads adj = [[] for _ in range(N+1)] for __ in range(M): A = int(input[ptr]) B = int(input[ptr+1]) C = int(input[ptr+2]) ptr +=3 adj[A].append((B, C)) adj[B].append((A, C)) # Read V array V = [] for i in range(N): V.append(int(input[ptr])) ptr +=1 # Dijkstra algorithm INF = float('inf') d = [INF] * (N+1) d[0] = 0 heap = [] heapq.heappush(heap, (0, 0)) while heap: dist_u, u = heapq.heappop(heap) if dist_u > d[u]: continue for v, w in adj[u]: if d[v] > d[u] + w: d[v] = d[u] + w heapq.heappush(heap, (d[v], v)) # Collect available cities cities = [] for i in range(1, N+1): if d[i] <= S: cities.append((d[i], V[i-1])) # V is 0-based # 0-1 Knapsack max_S = S dp = [0] * (max_S + 1) for (weight, value) in cities: for j in range(max_S, weight-1, -1): if dp[j - weight] + value > dp[j]: dp[j] = dp[j - weight] + value print(dp[max_S])if __name__ == '__main__': main() dp来记录最大财宝数量。转载地址：http://wknfk.baihongyu.com/