Problem:


ヘビの JOI 君 (Snake JOI)

問題

ヘビの JOI 君は，ある大きな屋敷に迷い込んでしまった．屋敷の住人に見つかる前に，屋敷を脱出しなければならない．

この屋敷には部屋が N 個あり，1, 2, ..., N の番号が付けられている．また，廊下が M 本あり，i 本目の廊下 (1 ≦ i ≦ M) は部屋 Ai と部屋 Bi を結んでいる．JOI 君はこれらの廊下をどちらの向きにも通ることができ，廊下 i を通るのには Di 分かかる．部屋と部屋の間を廊下を通る以外の手段で移動する方法はない．

この屋敷の部屋の温度はそれぞれ一定に調節されており，JOI 君にとって寒すぎるか，快適であるか，暑すぎるかである．JOI 君は，急な温度変化に対応できないため，最後に寒すぎる部屋を出てから X 分未満のうちに暑すぎる部屋に入ることはできない．同様に，最後に暑すぎる部屋を出てから X 分未満のうちに寒すぎる部屋に入ることもできない．

JOI 君は，移動中に部屋に入るとすぐに部屋から出なければならない．また，廊下の途中で引き返したり，廊下 i を Di 分より長い時間かけて通ることもできない．ただし，一度訪れた部屋にもう一度入ることや，一度使った廊下をもう一度使うことは許される．

JOI 君は現在部屋 1 にいる．この部屋は JOI 君にとって寒すぎる．JOI 君は屋敷の出口のある部屋 N に入ると，屋敷から脱出できる．

JOI 君が屋敷から脱出するのにかかる最短の時間を求めよ．

入力

入力は 1 + N + M 行からなる．

1 行目には，3 個の整数 N, M, X (2 ≦ N ≦ 10000, 1 ≦ M ≦ 20000, 1 ≦ X ≦ 200) が空白を区切りとして書かれている．これは，屋敷に N 個の部屋と M 本の廊下があり，JOI 君が温度変化に対応するのに X 分かかることを表す．

続く N 行のうちの i 行目 (1 ≦ i ≦ N) には，部屋 i の温度を表す整数 Ti (0 ≦ Ti ≦ 2) が書かれている．JOI 君にとって部屋 i は，Ti = 0 のとき寒すぎ，Ti = 1 のとき快適であり，Ti = 2 のとき暑すぎる．T1 = 0 であることが保証されている．

続く M 行のうちの j 行目 (1 ≦ j ≦ M) には，3 個の整数 Aj, Bj, Dj (1 ≦ Aj j ≦ N, 1 ≦ Dj ≦ 200) が空白を区切りとして書かれている．これは，廊下 j が部屋 Aj と部屋 Bj を結んでおり，通るのに Dj 分かかることを表す．同じ部屋の組を結ぶ廊下が複数ある可能性があることに注意せよ．

与えられる入力データでは，JOI 君が屋敷から脱出できることは保証されている．

出力

JOI 君が屋敷から脱出するのに最短で何分かかるかを表す整数を 1 行で出力せよ．

入出力例

入力例 1

8 10 4
0
1
1
2
1
1
2
0
1 2 1
1 3 1
2 3 3
2 4 5
3 4 1
4 5 1
5 6 1
5 8 1
1 7 2
7 8 2

出力例 1

9

入力例 2

15 25 4
0
1
1
0
2
1
0
1
1
2
0
0
1
0
1
8 11 1
7 10 1
12 14 1
3 8 1
1 5 1
3 9 1
3 8 1
1 5 1
6 15 1
11 12 1
2 14 1
7 10 1
11 12 1
5 13 1
2 8 1
1 4 1
2 11 1
5 6 1
1 13 1
6 12 1
5 10 1
9 13 1
4 10 1
3 12 1
7 13 1

出力例 2

6

入力例 1 では，部屋を 1 → 2 → 3 → 4 → 5 → 6 → 5 → 8 の順に移動するのが最短となる．

入力例 2 では，いくつかの部屋の組 (たとえば部屋 1 と部屋 5) を結ぶ廊下が複数ある．

情報オリンピック日本委員会作 『第 16 回日本情報オリンピック JOI 2016/2017 予選競技課題』



Sample input:
8 10 4
0
1
1
2
1
1
2
0
1 2 1
1 3 1
2 3 3
2 4 5
3 4 1
4 5 1
5 6 1
5 8 1
1 7 2
7 8 2


Sample output:
9

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
INF = 10 ** 20

def main():
  n, m, x = map(int, input().split())
  tlst = [int(input()) for _ in range(n)]
  edges = [[] for _ in range(n)]
  for _ in range(m):
    a, b, d = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append((b, d))
    edges[b].append((a, d))
  
  que = []
  heappush(que, (0, x, 0, 0)) #道のり、寒さ、暑さ、部屋番号
  dic = {}
  dic[(x, 0, 0)] = 0
  while que:
    total, ct, ht, node = heappop(que)
    for to, dist in edges[node]:
      new_ct = max(0, ct - dist)
      new_ht = max(0, ht - dist)
      t = tlst[to]
      if t == 1 or (t == 0 and new_ht == 0) or (t == 2 and new_ct == 0):
        new_total = total + dist
        if t == 0: new_ct = x
        if t == 2: new_ht = x
        if (new_ct, new_ht, to) not in dic or dic[(new_ct, new_ht, to)] > new_total:
          dic[(new_ct, new_ht, to)] = new_total
          heappush(que, (new_total, new_ct, new_ht, to))
  
  print(min([dic[(ct, ht, n - 1)] if (ct, ht, n - 1) in dic else INF for ct in range(x + 1) for ht in range(x + 1)]))

main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, M, X = map(int, input().split())
T = [int(input()) for i in range(N)]
G = [[] for i in range(N)]
for i in range(M):
    A, B, D = map(int, input().split())
    G[A-1].append((B-1, D))
    G[B-1].append((A-1, D))
INF = 10**9
dist = [[INF]*(2*X+1) for i in range(N)]
dist[0][-X] = 0

que = [(0, 0, -X)]
while que:
    cost, u, t = heappop(que)
    if dist[u][t] < cost:
        continue
    for v, d in G[u]:
        t1 = max(0, t - d) if t > 0 else min(0, t + d)
        if (t1 < 0 and T[v] == 2) or (t1 > 0 and T[v] == 0):
            continue
        t1 = [-X, t1, X][T[v]]
        if cost + d < dist[v][t1]:
            dist[v][t1] = cost + d
            heappush(que, (cost + d, v, t1))
print(min(dist[N-1]))