P4568 [JLOI2011] 飞行路线 分析 & 多层图

· · 个人记录

如果没有这个 k 的限制，本题可以降黑了（大雾）

可以用 DP 做，但因为 DP 本身就是 DAG 的一种其他形式，我们可以直接建一个新图。具体的，将原来的 n 个点变为 kn 个，每一个点 jn+i，代表使用 j 张免费票时的点 i。再找边：由 (j - 1)n + u 可以以零边权指到 (j - 1)n+v，由于无向，反着指也可以。同时，jn+u 和 jn+v 是以 w 边权联通的，其中 w 就是正常机票。

之后我们要求的就是 s 到 jn+s 的最短距离，\text{s.t.} \space j \in [0,k]（这是一个坑点）。这个题开空间也是个坑点，让我爆了好几遍紫。。