Codeforces 1801D The way home
看到 shortest paths 来做的。
首先有一个贪心的策略，对于当前点 \(u\) 若不能直接往后走则肯定是选择经过的点中 \(w_i\) 最大的加。
很好理解，证明就不需要了。
所以可以定义状态 \(f_{u, mx}\) 为 \(u\) 点最大能加的值为 \(h_{mx}\) 的最优状态，\(h\) 是 \(w\) 离散化后的数组。
接下来考虑最优状态要在哪些位置上优：
首先因为答案跟次数有关，所以肯定次数 \(c\) 会是之一，其次，若 \(c\) 相同，则肯定是走完上一条边剩的金钱越多越好（注意走一条边剩下的金钱肯定小于上一个状态对应的 \(h'_{mx}\)，因为到了 \(u\) 后 \(h_{mx}
\ge h'_{mx}\)，则在前面选的更多肯定不优），所以剩下的金钱 \(s\) 也要算上。
综合一下，则要满足 \(c\) 最小的同时 \(s\) 最大。
大致证一下为什么这么选择：
- \(c = c', s > s'\)，这肯定选择 \((c, s)\)；
- \(c < c'\)，则因为 \(s, s' < h'_{mx} \ge h_{mx}\)，所以 \(s + (c' - c)\times h_{mx} > s'\)，所以选择 \((c, s)\)。
然后发现这个 \((c, s)\) 的状态放在图上可以当做最短路来跑，直接跑就行。
时间复杂度 \(\mathcal{O}(T(nm\log_2 nm))\)。