在一个奇幻王国里，有 n 个城市（编号依次为 1 到 n ）和 m 条双向道路，第 i 条道路连接城市 u_i 和 v_i ，基础通行时间为正整数 w_i 。此外，王国中每个城市都存在 1 个中枢魔法石，每个魔法石有一个能量值，非负能量值的魔法石称之为「坏魔法石」，负数能量值的魔法石称之为「好魔法石」，坏魔法石会增加通行所需时间，好魔法石会减少通行所需时间（增加和减少的时间即为能量值的多少），如果好魔法石足够强力，甚至可以实现时间倒流。 坏魔法石将会强制生效，导致基础通行时间增加，无法被控制。 好魔法石可以控制，选择是否生效，但使用好魔法石的总次数存在限制，第 k 次使用好魔法石生效以后，之后将无法利用任何城市的好魔法石来减少通行时间。换句话说，单次行程中好魔法石总使用次数不超过 k 次。 魔法石不会消失，可以多次使用。 当你从城市 u 前往城市 v 时，路径的实际通行时间计算如下： 通行时间 = 城市 u 到城市 v 的道路基础通行时间加上城市 v 生效的魔法石能量值。 请计算从城市 1 到城市 n 的最小实际通行时间，注意，您可以重复经过城市和道路。特别地，如果无论如何都无法到达城市 n ，直接输出 NO 。
第一行输入三个整数 n,m,k (2 ≤ n ≤ 10^3; 1 ≤ m ≤ min\2 × 10^3,(n × (n-1)/2); 1 ≤ k ≤ 10^3) 。 第二行输入 n 个整数 a_1,a_2...,a_n (-10^5 ≤ a_i ≤ 10^5) ，其中 a_i 表示第 i 个城市的魔法石能量。 接下来 m 行，第 i 行输入三个整数 u_i,v_i,w_i (1 ≤ u_i,v_i ≤ n; u_i ≠ v_i; 1 ≤ w_i ≤ 10^5) ，表示城市 u_i 与城市 v_i 之间存在一条通行时间为 w_i 的路径。除此之外，保证任意两个城市间至多存在一条道路。 注意，本题不保证图的连通性，即可能存在两个城市无法通过任何路径互相到达的情况。
如果无论如何都无法到达城市 n ，直接输出 NO ，否则输出一个整数，表示从城市 1 到城市 n 的最小实际通行时间。
5 5 2 0 0 0 -10 0 1 2 1 2 3 1 3 5 1 1 4 6 4 5 1
-13
考点：图 · 堆 · 动态规划
数据规模 n ≤ 1e3 ｜ 限制 5 秒 / 256MB ｜ 标准输入输出
推荐方向：图
把关系抽象成点与边，再按问的类型选遍历/最短路/连通性算法。
思路框架（图 通法 · 非本题专属）
实现要点：注意是有向图还是无向图，无向图加边记得双向。
复杂度：时间 O(V+E) 遍历 / O(E log V) Dijkstra ｜ 空间 O(V+E)
该范式的通法易错点
对照本题
样例 1：输入 5 5 2 / 0 0 0 -10 0 / 1 2 1 / 2 3 1 / 3 5 1 / 1 4 6 / 4 5 1 → 输出 -13
在这个样例中，唯一的最优走法是， 1 → 2 → 3 → 5 → 4 → 5 → 4 → 5 ，实际通行时间为 1+1+1+(1-10)+1+(1-10)+1 。
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：2025年秋招-美团-算法策略端-第二批笔试。