BZOJ 1266 [AHOI2006] 上学路线 route


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

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


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

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

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

 

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1266 [AHOI2006] 上学路线 route


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,