BZOJ 2763 [JLOI2011] 飞行路线


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

题意:可以免费走 k 条边,求从 S 到 T 最短路...


建立分层图模型,将原图复制 k+1 层,每层代表剩余的免费次数,其余不变,层与层间将原图的边连下来,边权为 0,答案为每层 T 的最小值,注意 SPFA 会 TLE,边数和点数要开大一些...

A 掉后想到貌似一定是第 k+1 层的 T 是最小值,改了后交一发还是 A,但是显然这样是错的... 比如一个只有两个点,k 为偶数的图,显然偶数层都比奇数层优... 这说明什么.. 数据水啊啦啦啦

 

 

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

转载:转载请注明原文链接 - BZOJ 2763 [JLOI2011] 飞行路线


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

标签: , ,