本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-28 21:51:02

如果没有这个 $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]$（这是一个坑点）。这个题开空间也是个坑点，让我爆了好几遍紫。。