上述题目实际可以简化为：求一个节点 $1$ 到节点 $n$ 的路径，第 $k + 1$ 大的边权最小。是一个贪心的思想，很容易得出。

我们用 $f[u, k]$ 表示在节点 $1$ 到节点 $u$ 的路径中，用了 $k$ 次免费机会时，路径上最大的边权的最小值。

那么对于一个边 $u \to v$ 有以下状态转移：

1. 当这个边不免费时

   $f[v, k] = \min(f[v, k], \max(f[u][k], w(u, v)))$

2. 当这个边免费时

   $f[v, k + 1] = \min(f[v, k + 1], f[u, k])$

这个状态转移显然有后效性，因为题目给出的并不一定是 DAG，确定不了遍历顺序。对于这种情况，我们使用 SPFA 来进行状态的转移。这样的最短路问题被称为 分层图最短路。用 SPFA 算法的时间复杂度是 $O(tNP)$，其中 $t$ 应该是一个比较小的常数，实际可以 AC 这一题。