bzoj 2763: [JLOI2011]飞行路线 spfa 分层图

T的要死要活,卡常无果。然后感觉分层图是不是我先优先扩展本层,把本层扩展到最优然后再向其他层扩展,反复的松弛操作会少一些。然后我选择优先扩展本层,然后就A了。7000多ms。看网上题解,也是这么做,为什么他们这么快,几百毫秒就过去了,quq。。。

就dis[u][k]表示用k次免费机会到dis的最小距离,然后spfa就可以了。

发表评论