A ski area has marked checkpoints on the mountain and one-way runs between them. Every run always goes downhill, so you can never come back to a checkpoint you have passed: the map is a directed acyclic graph. Each run has a cost (effort, lift tokens, ...), and some checkpoints give a reward (a view, a café, a photo spot). A guest leaves from the lodge and must end at one of the finish areas. Find the best score they can get.
Write max_ski_score(runs, rewards, start, finishes) -> int | None:
runs: a list of[frm, cost, to]triples, a one-way run from checkpointfrmto checkpointtocostingcost(0 <= cost <= 10^4). Checkpoints are strings. There may be several runs between the same two checkpoints.rewards: a list of[checkpoint, reward]pairs (0 <= reward <= 10^4), each checkpoint listed at most once. Checkpoints not listed have reward0. A listed checkpoint may appear in no run at all.start: the lodge.finishes: a list of finish checkpoints.
A path starts at start, follows runs, and ends at any checkpoint in finishes. It may pass through other finish checkpoints on the way. Its score is the sum of the rewards of every checkpoint on it (including start and the last one) minus the sum of the costs of the runs it uses. If start is itself a finish, the path with no runs counts, scoring start's reward.
Return the highest score over all paths, or None if no finish can be reached from start.
runs = [["lodge", 4, "pines"], ["lodge", 1, "bowl"], ["pines", 2, "base"],
["bowl", 6, "base"], ["bowl", 1, "cafe"], ["cafe", 1, "base"]]
rewards = [["pines", 5], ["cafe", 7], ["base", 2]]
max_ski_score(runs, rewards, "lodge", ["base"]) # 6 lodge->bowl->cafe->base: 7 + 2 - 3
max_ski_score(runs, rewards, "lodge", ["pines", "cafe"]) # 5 lodge->bowl->cafe: 7 - 2
max_ski_score(runs, rewards, "base", ["lodge"]) # None
max_ski_score([], [["lodge", 3]], "lodge", ["lodge"]) # 3
Constraints: up to 10^5 runs and checkpoints. The number of different paths can be astronomically large, and a single path may use 10^5 runs, so neither listing paths nor deep recursion will work.
Show hint
the best score to reach a checkpoint only depends on the best scores of the checkpoints with runs into it. Process checkpoints in topological order (Kahn's algorithm, with a queue, no recursion), keeping best[v] for those reachable from start, and relax each run once.