最不会的一集。

B

题意

Alice 喜欢旅游，在这个假期里他将沿着公路骑行。
可供 Alice 选择的道路构成了一张连通无向图，Alice 的起点位于 \(1\) 号点，终点位于 \(n\) 号点，每条道路有一个困难度 \(v_i\)。定义一条路径的疲劳度为他路上经过的所有道路的困难度的最大值。
一开始 Alice 有 \(k\) 点体力，在通过一条道路时，他可以选择消耗若干点体力值，每消耗一点，道路的困难度也会降低 \(1\)，但一条道路的困难度不能低于 \(0\)。
Alice 想知道他这次旅程的最小疲劳度。

首先最大最小肯定有一个二分壳子，二分最大值 \(val\)，看怎么写 check()。
对于每一次 check()，边权 \(d\) 小于等于 \(val\) 的并不会消耗体能，而 \(d\) 大于 \(val\) 的会消耗 \(val-d\) 的体能。
然后就是从 \(1\) 到 \(n\) 跑最短路，跑出来的就是最小体能消耗。时间复杂度 \(O(m\log m\log |V|)\)，其中 \(V\) 是值域。