#洛谷 通往奥格瑞玛的道路

题面对我来说貌似有毒,看了很长时间才看懂这是一个最大值最小问题 果断二分答案。

主要思想是先跑一边Bellman-Ford+队列优化(也叫SPFA)把二分值设定成+∞ 然后看一看如果到终点的花费大于血量就输出AFK(away from keyboard)

如果可行就快排点权+二分下标 如果当前二分值可以跑到终点(跑SPFA判)就向左找(升序sort),不然就向右找。

跑SPFA的时候传一个upat也就是二分值 把点权大于二分值的点都判(删)掉 

 

还有一点就是最后还要判一下二分值。链式前向星+SPFA+手写Sort,没有注释……