Submission #31709937

---

Source Code Expand

import heapq
n, m, x = map(int, input().split())
t = [0] * n
for i in range(n):
    t[i] = int(input())
e = [[] for i in range(n)]
for i in range(m):
    a, b, d = map(int, input().split())
    e[a - 1].append([b - 1, d])
    e[b - 1].append([a - 1, d])
cost = [[[10 ** 9] * (x + 1) for j in range(2)] for i in range(n)]
# cost[i][j][k] = 今頂点 i にいて以前に j (0: 寒すぎる，1: 暑すぎる) の部屋にいて，温度差の大きい部屋に入れるようになるまでの残り時間が k であるときの，ここまでの経過時間の最小値
q = []
cost[0][0][x] = 0
heapq.heappush(q, [0, 0, 0, x])
while len(q) != 0:
    d, v, a, b = heapq.heappop(q)
    if cost[v][a][b] != d:
        continue
    for u, c in e[v]:
        if t[u] == 0:
            if a == 1 and b - c > 0:
                continue
            if cost[u][0][x] > d + c:
                cost[u][0][x] = d + c
                heapq.heappush(q, [d + c, u, 0, x])
        if t[u] == 1:
            if cost[u][a][max(0, b - c)] > d + c:
                cost[u][a][max(0, b - c)] = d + c
                heapq.heappush(q, [d + c, u, a, max(0, b - c)])
        if t[u] == 2:
            if a == 0 and b - c > 0:
                continue
            if cost[u][1][x] > d + c:
                cost[u][1][x] = d + c
                heapq.heappush(q, [d + c, u, 1, x])
answer = 10 ** 9
for i in range(x + 1):
    answer = min(answer, cost[n - 1][0][i], cost[n - 1][1][i])
print(answer)

Submission Info

Judge Result