Best-scoring ski run through a trail map

A ski area has mapped its one-way trails between named checkpoints. The trail map has no cycles: once you ski down a trail you can never get back to where you were.

Every trail has a cost to ski it, and some checkpoints award points when you arrive. The skier starts at the checkpoint START and may finish at any checkpoint whose name begins with END_.

The net score of a run is the sum of the rewards of every checkpoint on it (including START and the finish) minus the sum of the costs of the trails it uses.

Implement:

def max_net_score(routes: list[list], checkpoints: list[list]) -> int | None

• routes[i] = [from, cost, to] is a one-way trail from from to to with a non-negative integer cost.
• checkpoints[j] = [name, reward] gives the reward for arriving at name. A checkpoint that is not listed has reward 0.
• Return the highest net score over all runs from START to any END_ checkpoint. The answer may be negative. Return None if no finish can be reached from START.

Constraints

• Up to 10^5 checkpoints and 2 * 10^5 trails.
• The graph is a DAG. There may be more than one trail between the same two checkpoints.
• Rewards fit in a 32-bit integer.

Example 1

routes = [["START", 3, "A"], ["START", 1, "B"], ["A", 2, "END_1"],
          ["B", 4, "C"], ["C", 1, "END_1"], ["C", 6, "END_2"]]
checkpoints = [["A", 8], ["B", 2], ["C", 9], ["END_1", 5], ["END_2", 14]]

Output: 14. The run START -> B -> C -> END_2 scores -1 + 2 - 4 + 9 - 6 + 14 = 14. The other runs score 8 (START -> A -> END_1) and 10 (START -> B -> C -> END_1).

Example 2

routes = [["START", 5, "END_X"]]
checkpoints = [["END_X", 2]]

Output: -3. The only run costs more than it earns, but it is still the best run.

Be ready to return the route itself, and to discuss what changes if each trail also takes time and the skier has a time limit.