题解 | 魔法路径

from heapq import heappop, heappush
from math import inf
import sys

def solve_least_time(dis, g, n, mag, k, H):
    h = [(0, 1, 0)]

    while h:
        d, i, used_k = heappop(h)
        if d > dis[i][used_k]:
            continue
        
        for j, w in g[i]:
            if used_k < k and mag[j] < 0:
                nd =  d + w + mag[j] + H
                if nd < dis[j][used_k + 1]:
                    dis[j][used_k + 1] = nd
                    heappush(h, (nd, j, used_k + 1))

            nd = d + w + max(mag[j], 0)
            if nd < dis[j][used_k]:
                dis[j][used_k] = nd
                heappush(h, (nd, j, used_k))




if __name__ == "__main__":
    n, m, k = map(int, input().split())
    mag = [0] + list(map(int, input().split()))  
    H = -min(min(mag[1:]), 0)
    g = [[] for _ in range(n+1)]  # 按照1--n编号存储
    for _ in range(m):
        u, v, w = map(int, input().split())
        g[u].append((v, w))
        g[v].append((u, w))
    dis = [[inf] * (k + 1) for _ in range(n + 1)]
    dis[1][0] = 0
    solve_least_time(dis, g, n, mag, k, H)
    # ans = min([dis[n][i] - H * i for i in range(0, k+1) if dis[n][i] < inf])
    ans = inf
    for i in range(k+1):
        if dis[n][i] < inf:
            ans = min(ans, dis[n][i] - H * i)
    
    if ans < inf:
        print(ans)
    else:
        print("NO")