大家好！今天我来讲广度优先搜索了awa
但是我不会讲啊qwq，那只能放几道习题边做边讲了
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
P2446 [SDOI2010] 大陆争霸
哇！看起来好麻烦……既要尽快到达指定地点自爆，又要等别的机器人破开保护……这怎么做啊！
我们可以进行 nnn 次，每次跑一遍最短路，然后对破坏节点的时间取个max，但是这样是 O(nmlogn)O(nmlogn)O(nmlogn) 的，过不了啊！
先别急，我们回想一下最短路是怎么求的。
我们开个优先队列，遍历每一条边，如果新的距离小于当前距离，就把它放进优先队列。这样就能保证每次取出来的时间是上升的了。
再看到这道题，就算要对保护节点取max，还是没有打破遍历时间是上升的这个规则。所以，对于每个出队（被破坏）的点，我们可以分别遍历它能到达的点和它所保护的点，如果时间更优了，那么就更新距离并入队。这样就是对的了，时间复杂度也做到了 O(mlogn)O(mlogn)O(mlogn)。
这题真好玩！
P4366 [CODE+#4] 最短路
这道题看上去直接优先队列广度优先搜索就行了……但是真的这么简单吗？
重新读一遍题，发现这题的边数高达 O(n2+m)O(n^2+m)O(n2+m)！数据范围也是惊人的 10510^5105 TwT
a→ba\to ba→b 原来的最短路其实就是看它们每一位是否不同，那每两个点连一条边实在太浪费了！
我们可以将点 iii 连向所有只有一位不同的点，这样也可以看它们每一位是否不同，和之前的图等价的，但是边数只有 O(nlogn)O(nlogn)O(nlogn)！
然后就可以开心地优先队列广搜了~~~
P2993 [FJOI2014] 最短路径树问题
题目是给定一张无向图，求出它字典序最小的最短路径树，后面叽里咕噜说一大串听不懂，就不讲啦~
那怎么求字典序最小的最短路径树呢？
我们求出最短路径后，将邻居按编号排序，从1开始dfs，遇到可能是最短路径的边就加入。这样贪心肯定是对的，而且也能保证字典序最小。
老师还讲了P2934和P6545，但是我太弱了听不懂……
P9370 [APIO2023] 赛博乐园 / CYBERLAND
对于时间可以无限次消成 000 的点，那先到达这个点然后再去终点和以它为源点去终点没有区别，所以可以一起加入源点广搜。
那么对于时间减半的点呢？最多只能用 kkk 次，感觉有点不太好做……
这时候，就要用到，大名鼎鼎的，分层图最短路！
将图分为 kkk 层，使用能力相当于往上走一层，这么建图和DP一样，没有后效性，也就是不会影响之前的点。
这样，我们就有了 O(kmlogn)O(kmlogn)O(kmlogn) 的做法，但是 k≤106k\le 10^6k≤106 啊……
我们发现，当 kkk 很大的时候，前面的时间就算很长，也相当于消成没有了！所以我们只要找到这个临界点，大概是 707070，对 kkk 取个min就行了！
P2865 [USACO06NOV] ROADBLOCKS G
最短路都很好做，直接优先队列广搜就行了。但是次短路呢？为什么会有人研究第二短的路啊！！！
但其实也不算太难，在最短路的基础上稍微改改就行了。
具体来说，就是再开一个数组记录最短路，对于当前队列，如果有一条边更优，那它就成为最短路，原先的最短路成为次短路；否则它就和次短路比较qwq
但是！这里就不能标记vis了！因为有可能这个时候它的次短路还没更新完！这时，我们的剪枝就得改成当前距离小于当前次短路了。这样，由于可以来回走，每个点最多会被松弛两次（最坏情况第二次是从自己往返走一条边回来），时间复杂度是 O(mlogn)O(mlogn)O(mlogn) 不变。
P2371 [国家集训队] 墨墨的等式
啊？这题不是解方程吗？？？
看到这里，你或许也会有和我一样的疑惑。
但是，这和普通的多元一次方程有个不一样的地方，就是它的所有 xxx 都是非负的！
怎么做呢？感觉好难啊/O0O\
有个非常神奇的做法，就是选 a1a_1a1 ，把其它的都模上它，然后发现我们只要枚举 kkk，看满足其它 aia_iai 之和模这个 a1a_1a1 等于 kkk，并且 a1a_1a1 的和最小的情况就行了！
具体地，我们可以将点 kkk 连向 (k+ai) mod a1(k+a_i)\bmod a_1(k+ai )moda1 ，权值为 aia_iai 的边，跑一遍优先队列广搜就行了。
但是再次观察我们发现，并不需要广搜！每个 aja_jaj 建边都会形成若干个环，随便找一个点照着环跑两圈更新最短路就可以了！
这样，复杂度就是 O(na1)O(na_1)O(na1 ) 的。
P9140 [THUPC 2023 初赛] 背包
这……不是背包吗？
但是 VVV 这么大……感觉dp不动啊QAQ
我们想一下有没有什么好方法可以缩小范围？
最优解肯定是使劲选一个物品，那这个物品是什么呢？显然是性价比最高的啦~
假设性价比最高的物品是 xxx。
那其他的物品呢？
其实，可以当成上面的问题做，vvv 当成 aaa，ccc 当成权值，跑最长路。只不过，如果连向超过的边，要减去 cxc_xcx 。
然后，按照我上面说的跑两圈就可以 O(nvx)O(nv_x)O(nvx ) 解决了 awa
CASHIER EMPLOYMENT POJ - 1275
设 xix_ixi 为 iii 点时需要雇佣的人。
然后我们会发现题目的限制要转成 xi+xi−1+xi−2+...+xi−7≥R(i)x_i+x_{i-1}+x_{i-2}+...+x_{i-7}\ge R(i)xi +xi−1 +xi−2 +...+xi−7 ≥R(i)，式子看起来太多了，怎么办？
说句闲话，帅童在这里卡住了，哈哈。
我们可以充分发扬人类智慧，开个 yiy_iyi 记录 x1x_1x1 到 xix_ixi 的和，这样，就转化成 yi−yi−8≥riy_i-y_{i-8}\ge r_iyi −yi−8 ≥ri 了！
当然，如果 i<8i\lt 8i<8，要反着算：y24−y16+i+yi≥R(i)y_{24}-y_{16+i}+y_i\ge R(i)y24 −y16+i +yi ≥R(i)。但是这三个项，还是太多了！
没事，我们最终求的是 y24y_{24}y24 的最小值，所以只需要二分 y24y_{24}y24 的值 ppp，判断可不可以就行了。
然后再加上 xix_ixi 的限制 0≤yi−yi−1≤max(xi)0\le y_i-y_{i-1}\le max(x_i)0≤yi −yi−1 ≤max(xi )，以及 p≤y24−y0≤pp\le y_{24}-y_0\le pp≤y24 −y0 ≤p，就可以了，为什么？
因为我们发现列的式子都满足 ax−ay≥za_x-a_y\ge zax −ay ≥z，这个和最短路的 disx≥disy+zdis_x\ge dis_y+zdisx ≥disy +z 很像，所以按要求建图跑最短路（如果有的话）就能求出解了！
当然，因为边权有负的，所以应该跑不能用优先队列的 vis 标记也要打 nnn 次的那个广搜。而且图很小，所以能过。
这样子是 O(242logn)O(24^2logn)O(242logn) 的。
