[洛谷P1462]通往奥格瑞玛的道路[二分答案]

这道题要求最大收费点的最小值,明显是二分答案
二分check(maxf)函数目标:判断能否在 最大收费点小于maxf 的条件下,走到终点
能则缩小maxf, 否则只能是更大的maxf
具体实现: dijkstra松弛的时候加个判断 点权小于maxf 就行了

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址