You’re in a ski tournament, where you ski from the top of the mountain to one of the finish checkpoints at the bottom. There are multiple routes with checkpoints, and each checkpoint has an associated point value.
Your total score = points from all checkpoints you visited – time of your travel.
Given:
- A list of lists, each containing
[start_cp, end_cp, time_to_travel] - A list of lists, each containing
[cp, point]
Goal:
Find the maximum score that you can collect during the tournament and print out the optimal path.
这道题本质上是一个带权有向图上的最优路径问题：每个 checkpoint 既有得分点数，又可能通过路径消耗时间，因此目标不是最短路，而是在“节点收益 – 边权成本”的组合下找到从起点到终点的最大总分，并输出对应路径。常见做法是把路线看作图结构，用动态规划或拓扑序在有向无环图中累计最优分值；如果需要重建路径，可以记录每个节点的前驱节点。关键在于正确合并 checkpoint 的分数和 travel time 两部分，并在所有可达终点中选择总得分最高的一条。
正文完
