滑雪问题

2026/8/9 21:31:16 拓冰建站浏览量

是一个滑雪选手从高山上往下滑，会遇到不同的checkpoint，每一个checkpoint有自己的point，然后每个edge有distance。经过每一个checkpoint所得到的score是通过一个包含point和distance的式子算出来的（比如2 * point +distance之类的）。最终求从最高点往下滑能得到的最大score是多少

 1 from collections import deque
 2 
 3 def calculate_max_scores(points, graph, start_node):
 4     max_scores = {node: -float('inf') for node in points}
 5     
 6     if start_node in max_scores:
 7         max_scores[start_node] = 2 * points[start_node]
 8 
 9     queue = deque([start_node])
10     
11     while queue:
12         u = queue.popleft()
13         if u in graph:
14             for v, dist in graph[u]:
15                 new_score = max_scores[u] + (2 * points[v] + dist)
16                 if new_score > max_scores[v]:
17                     max_scores[v] = new_score
18                     queue.append(v)
19                     
20     return max_scores
21 
22 if __name__ == "__main__":
23     points_data = {
24         'A': 5, 'B': 7, 'C': 6, 'D': 2, 
25         'E': 1, 'F': 7, 'H': 7, 'I': 3, 'J': 2
26     }
27 
28     graph_data = {
29         'A': [('B', 2), ('C', 3)],
30         'B': [('D', 5), ('E', 6)],
31         'C': [('E', 4), ('F', 4)],
32         'D': [('H', 7)],
33         'E': [('H', 6)],
34         'F': [('J', 3)],
35         'H': [('I', 1), ('J', 2)],
36         'I': [],
37         'J': []
38     }
39 
40     results = calculate_max_scores(points_data, graph_data, 'A')
41 
42     print("--- 节点最大得分统计 ---")
43     for node, score in results.items():
44         if score != -float('inf'):
45             print(f"节点 {node}: {score}")
46             
47     print("\n--- 最终目标 ---")
48     final_max = max(results['I'], results['J'])
49     print(f"到达 I 或 J 的最高分是: {final_max}")

建站实战干货

滑雪问题