BZOJ 2763 [JLOI2011] 飞行路线

发布于 2017-06-15  119 次阅读


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

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


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

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

 

 


一个非常弱的准退役OIER