第四周题解

林克的综合难题：
links！

时空门票与跃迁
考虑贪心，从最便宜的门票开始买，注意在这之前先排序。每次先判断，如果将门票全买了还没到我们需要的门票数就直接全买。然后记下后面每张门票多花的钱，如果这次买票之后的总票数能到我们需要的总票数就买我们还需要的门票数。

最短路简单的变化
首先求出 1,n 两个点的单源最短路径。这 k 个特殊点中，我们另第 i 个特殊点到 1 的距离为 xi，到 n 的距离为 yi 。设答案是连接 i , j 两点。则我们要： maximize{min⁡(xi+yj,xj+yi)}

不妨设 xi + yj < xj + yi ，则有 xi − xj < yi − yj 。因此我们将每个点按照 x 排序，维护第 i 个点到第 n 个点 y 的最大值。假设取了第 i 个点的 xi ，则 j 点一定在 i 点的后面。我们遍历一遍取哪个 i 即可。
CD:https://www.luogu.com.cn/article/sbil8lz7
EF:https://www.luogu.com.cn/article/a91o0v5z