题面 P3645 [APIO2015]雅加达的摩天楼 Solution 与其说这题是分块妙题,我更倾向于把这题称为分层图妙题。 这题有一个一眼贪心做法:对于每只doge,我们都暴力地去建它连向它能跳到的点的边,边权为跳的次数。然后直接求一遍单元最短路即可。 很显然,这玩意的边的数量是$O(n^2)$的,求一遍最短路的复杂度达到了惊人的$n^2logn^2$ 这显然是要T飞的,但是我们会从中发现一个问题:既然一个doge的跳跃是多步的,那我们能否直接把几步拆开来,然后省略重复的边? 例如: 优化为: 这样做看起来很星…