魔法路径__牛客网

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

$\hspace{15pt}$ 坏魔法石将会强制生效，导致基础通行时间增加，无法被控制。
$\hspace{15pt}$ 好魔法石可以控制，选择是否生效，但使用好魔法石的总次数存在限制，第 $k$ 次使用好魔法石生效以后，之后将无法利用任何城市的好魔法石来减少通行时间。换句话说，单次行程中好魔法石总使用次数不超过 $k$ 次。
$\hspace{15pt}$ 魔法石不会消失，可以多次使用。

$\hspace{15pt}$ 当你从城市 $u$ 前往城市 $v$ 时，路径的实际通行时间计算如下：
$\hspace{15pt}$ 通行时间 = 城市 $u$ 到城市 $v$ 的道路基础通行时间加上城市 $v$ 生效的魔法石能量值。
$\hspace{15pt}$ 请计算从城市 $1$ 到城市 $n$ 的最小实际通行时间，注意，您可以重复经过城市和道路。特别地，如果无论如何都无法到达城市 $n$ ，直接输出 $\text{NO}$ 。

$\hspace{15pt}$ 第一行输入三个整数 $n,m,k$ $\Big(2 \leqq n \leqq 10^3;$ $1 \leqq m \leqq \min\left\{2 \times 10^3,\tfrac{n \times (n-1)}{2}\right\};$ $1 \leqq k \leqq 10^3\Big)$ 。
$\hspace{15pt}$ 第二行输入 $n$ 个整数 $a_1,a_2\dots,a_n \left(-10^5 \leqq a_i \leqq 10^5\right)$ ，其中 $a_i$ 表示第 $i$ 个城市的魔法石能量。
$\hspace{15pt}$ 接下来 $m$ 行，第 $i$ 行输入三个整数 $u_i,v_i,w_i$ $\big(1 \leqq u_i,v_i \leqq n;$ $u_i \neq v_i;$ $1 \leqq w_i \leqq 10^5\big)$ ，表示城市 $u_i$ 与城市 $v_i$ 之间存在一条通行时间为 $w_i$ 的路径。除此之外，保证任意两个城市间至多存在一条道路。

$\hspace{15pt}$ 注意，本题不保证图的连通性，即可能存在两个城市无法通过任何路径互相到达的情况。

魔法路径

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题