BZOJ 1266 [AHOI2006] 上学路线 route

发布于 2017-05-26  157 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1266

题意:一张无向图,边有时间,费用两个权值,第一问从 1 到 n 最短时间,第二问删除一些边使得最短时间变长的最小权值....


第一问随便最短路... 为了方便搞了个 floyd....

考虑第二问怎么搞... 其实是个萨博题... 却想了好半天.... 最短路变长只要旧最短路走不通就行了... 那么针对旧最短路建图,最小割,结束...

评论区说有重边... 实际上并没有,或者不需要处理.. 代码如下:

 

 


一个非常弱的准退役OIER