rt qwq

甚至是最优解

先把每条边的边权设成它的排名

然后最后那条路径一定是所有长度<=D的路径中，边权最大值最小的路径

所以找到这条路径，设边权最大值为 max，然后就用这条边权最大的边补齐当前长度和 D 之间的差，其它所有边权>max的边全部设成inf

然后就过了。点名批评 @mfeitveer 试图蒯我代码（考后），然后卡常还卡不过我 记录2

但是我考场上输入写错了，荣获24pts /dk

rt qwq

就是纯粹的暴力，没有剪枝。判了一下重边和自环。

因为 $∑k < 10^6$，所以 check() 的总复杂度是正确的

这几天数据是真的不行 希望以后的出题人能够引以为戒

rt qwq

大体思路就是维护一个队列q存储当前知道答案的区间，然后取出对首的区间，往左和往右分别找到并拓展到mex，然后再把这两个新区间加入队列

这玩意看上去会像是一个指数复杂度的东西，但是完全跑不满，可以过subtask3。判了重之后复杂度不高于 $O(n^3\log n)$（使用map带一个log），可以直接切掉本题

但是作为一场以noip为难度定位的模拟赛的T2，这种东西都没卡掉那就是出题人的问题了

如果有人能够证明这玩意的复杂度正确，那当我没说

（刚才我在标题里写的是指数级复杂度，有些小错误，已经修正）

rt qwq

思路就是如果目标地点在两人围成的区间之外，就贪心地让最近的人移过去，否则就分别搜索两个人移动到目标的情况

如果一定要让我对我这个算法分类，我认为这是一种写得非常奇怪的记忆化搜索

容易证明这个东西复杂度的上限是 $O(n^3)$ (两个人位置的取值分别有 $n$ 种情况，然后又要扫 $n$ 遍)

所以我认为这个题目的数据造得并不是很优秀，希望以后的出题人们能够引以为戒，防止我这种申必写法卡过去（还跑得贼快