P3390.第3题-奇幻王国魔法石
题目内容
在一个奇幻王国里，有 n 个城市(编号依次为 1 到 n )和 m 条双向道路，第 i 条道路连接城市 ui 和 vi ， 基础通行时间为正整数 wi 。此外，王国中每个城市都存在 1个中枢魔法石，每个魔法石有一个能量值，非负能量值的魔法石称之为「坏魔法石」，负数能量值的魔法石称之为「好魔法石」，坏魔法石会增加通行所需时间，好魔法石会减少通行所需时间(增加和减少的时间即为能量值的多少)，如果好魔法石足够强力，甚至可以实现时间倒流。
坏魔法石将会强制生效，导致基础通行时间增加，无法被控制。
好魔法石可以控制，选择是否生效，但使用好魔法石的总次数存在限制，第 k 次使用好魔法石生效以后，之后将无法利用任何城市的好魔法石来减少通行时间。换句话说，单次行程中好法石总使用次数不超过 k 次。
魔法石不会消失，可以多次使用。
当你从城市 u 前往城市 v 时，路径的实际通行时间计算如下：
通行时间=城市 u 到城市 v 的道路基础通行时间加上城市 v 生效的魔法石能量值。
请计算从城市 1 到城市 n 的最小实际通行时间，注意，您可以重复经过城市和道路。特别地，如果无论如何都无法到达城市 n ，直接输出 NO 。
输入描述
第一行输入三个整数 n,m,k(2≤n≤103;1≤m≤min{2×103,2n×(n−1)};1≤k≤103)
第二行输入 n 个整数 a1,a2,...,an(−105≤ai≤105)，其中 ai 表示第 i 个城市的魔法石能量。
接下来 m 行，第 i 行输入三个整数 ui,vi,wi(1≤ui,vi≤n;ui=vi;1≤wi≤105) ，表示城市 ui 与城市 vi 之间存在一条同行时间为 wi 的路径。除此之外，保证任意两个城市之间至多存在一条道路。
注意，本题不保证图的连通性，即可能存在两个城市之间无法通过任何路径互相到达的情况。
输出描述
如果无论如何都无法到达城市 n ，直接输出下 NO ，否则输出一个整数，表示从城市 1 到城市 n 的最少实际通行时间。
样例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 。
