单调队列个毛线~前缀和+后缀和小常数AC。

本题是出题人故意用堆优化Dijkstra去卡SPFA的……
那几个挂掉的提交都来自失败的SPFA作死尝试……
注意两点：①用vector存邻接表会RE（为何不是MLE？）②数据基本是随机生成的，也就是说步长一般会很大……所以Dijktra占便宜（把那两个点算出来就可以直接跳出），但SPFA+卡时WA了……

神犇们是什么做的

回复 @Asm.Def :
经大神点拨重交了一遍就过了

回复 @St.Burning\ : codevs

为什么我的代码得不到满分，请帮助

回复 @cstdio :
强烈呼吁萌帝把这题难度改为8星！！！

这个单文件5组数据，20s是为了吓人用的么……
出题人放学别走(╯‵□′)╯︵┻━┻
另外，必须一直坐电梯，不能在同层自由走动或者下楼……那个“下楼自行解决”的设定估计仅仅是为了世界观的严谨……

树链剖分维护“一段路径/DFS序列内的背包和”……

题解地址：
比例简化题解

题解地址：
珠心算测验题解

理论上是平面图最大流转最短路，但……
“网络流的时间复杂度估计是很悲观的”——光神@闫星光

回复 @ch3coooh :
野生的3s出现了！！！！！！！！！