前言
你只记得，努力之后，是九死一生。却忘了，若不努力，便是十死无生。
感觉今天的题充其量也是一堆典题，可是我还是菜的不会几道，做过的都不会了。。
Cheap Robot
显然，你可以先从每个充电站出发跑一个多源最短路，得到每个点 \(x\) 到其最近的充电站的距离 \(dis_x\)。
有一个更加显然的东西是，你无论当前走到了哪个点，假设是 \(x\)，当前剩余容量为 \(y\)，你一定要满足 \(dis_x\le y\)。
同理，如果你要到达一个点，那么油箱容量也必须 \(\ge dis_x\)。
那么，你发现，对于任意一条边 \((u,v,w)\)，经过他所需的最小容量就是 \(dis_u+dis_v+w\)，你要求的就是对于 \(a\to b\) 的每条路径上经过每条边的最小容量最大值的最小值。
显然直接上 \(\texttt{Kruskal}\) 重构树就直接秒了。
有序奶牛
题目保证按照输入的偏序建边一定是个 \(\texttt{Dag}\)，而我最开始根本就没有发现这件事情。
一个比较直观的删边方法就是你再删掉这条边之后，剩下的边仍然可以使得这条边的起点到达终点。
具体实现就是你先跑一边拓扑序，然后对于每一条边 \(u,v\) 按照 \(\text{topo}_u\) 为第一关键字，\(\text{topo}_v\) 为第二关键字从小到大排序。
然后你按照排序后的顺序遍历每条边，更新连通性即可，可以通过 \(\texttt{Bitset}\) 做到 \(\mathcal{O}(\frac{nm}{w})\)。
变换序列
按照题目中给得 \(D(i,j)\) 的定义和具体的值，每个点最多连出去四条边，然后直接跑最小字典序完美匹配即可。
字典序的话你直接对于边权最小到大遍历即可。
Dynamic Shortest Path / 动态最短路
挺不错的一道题。
暴力思路是你对于每次操作之后跑一遍 \(\texttt{Dijkstra}\)，复杂度 \(\mathcal{O}(q\times m\log n)\)，直接炸掉。
我们发现这个 \(\log n\) 非常难受，想一下有没有办法把他搞掉。
有一个比较重要的东西是，如果 \(\forall x\in[1,n],dis_x\le V\)，那么你可以把堆优化 \(\texttt{Dijkstra}\) 改成用桶排优化，复杂度可以做到 \(\mathcal{O}(V+n+m)\)。
