解题思路

• 将状态扩展为分层图：层编号为已使用好石次数 $c\in[0,k]$，状态为 $(v,c)$。

• 转移分两类（设到达点为 $v$，边基础代价为 $w$）：

  • 不用好石：层内转移 $(u,c)\to(v,c)$，代价 $w+\max(a_v,0)$（坏石必加、好石不加）。
  • 用好石（仅当 $a_v<0$ 且 $c<k$）：跨层 $(u,c)\to(v,c+1)$，代价 $w+a_v$（可能为负）。

• 由于层内边权均为非负（至少 $w\ge 1$），可用 $k+1$ 次 Dijkstra 的分层松弛套路：

  • 先在 $c=0$ 层，设 $d_0[1]=0$ 其余为无穷，跑一次 Dijkstra（仅用层内转移，代价 $w+\max(a_v,0)$）。

题目内容

在一个奇幻王国里，有 $n$ 个城市(编号依次为 $1$ 到 $n$ )和 $m$ 条双向道路，第 $i$ 条道路连接城市 $u_i$ 和 $v_i$ ， 基础通行时间为正整数 $w_i$ 。此外，王国中每个城市都存在 $1$个中枢魔法石，每个魔法石有一个能量值，非负能量值的魔法石称之为「坏魔法石」，负数能量值的魔法石称之为「好魔法石」，坏魔法石会增加通行所需时间，好魔法石会减少通行所需时间(增加和减少的时间即为能量值的多少)，如果好魔法石足够强力，甚至可以实现时间倒流。

坏魔法石将会强制生效，导致基础通行时间增加，无法被控制。

好魔法石可以控制，选择是否生效，但使用好魔法石的总次数存在限制，第 $k$ 次使用好魔法石生效以后，之后将无法利用任何城市的好魔法石来减少通行时间。换句话说，单次行程中好法石总使用次数不超过 $k$ 次。