Submission #52159603

---

Source Code Expand

import heapq
INF = pow(10,20)                        # 無限大とする値。距離や頂点数から考えて十分大きい値にすること

H,W = map(int, input().split())
edge = [["#" for _ in range(W+2)]] 
center = [["#"] + list(input()) + ["#"] for i in range(H)]
A = edge + center + edge

medicines = dict()

N = int(input())
for _ in range(N):
    R,C,E = map(int, input().split())
    medicines[(R,C)] = E

# どこかのマスを通り過ぎてから戻ることはない
# → あるマスについて薬があったとき、エネルギーが増えるなら使用する。増えないなら使用しない。
# エネルギーは＋でなく、=になる → 戻ってもう一回使うのと等価
# 経路が関係あるのでダイクストラっぽい

# 始点・終点を得る
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j] == "S":
            Si,Sj = i,j
        elif A[i][j] == "T":
            Ti,Tj = i,j

# ダイクストラ法
energy = [[-1 for _ in range(W+2)] for _ in range(H+2)]  # あるマスでの残存エネルギー量最大値
energy[Si][Sj] = 0
hq = [(0,Si,Sj)]    # 優先度付きキューに(残りエネルギー量、始点座標)を追加
heapq.heapify(hq)

while len(hq)!=0:
    e,i,j = heapq.heappop(hq)           # 優先度付きキューから残存エネルギーが多い方から頂点を取り出し
    e *= -1                             # 多い方から取り出しのために-1倍しているので直す

    if i == Ti and j == Tj:
        print("Yes")
        exit()
    
    if energy[i][j] == e:               # (Q(v)←altではなく、更新毎に追加しているので、不要パターンがある。最短の場合のみ処理)
        if (i,j) in medicines:
            # 薬があるなら利用有無を検討
            if e < medicines[(i,j)]:
                e = medicines[(i,j)]
                energy[i][j] = e

        if e > 0:
            for u,v in [(1,0),(-1,0),(0,1),(0,-1)]: # 取り出した頂点から移動できるすべての点に対して
                if energy[i+u][j+v] < e - 1 and A[i+u][j+v] != "#":
                    # 残存エネルギーが増加するなら更新
                    energy[i+u][j+v] = e - 1
                    heapq.heappush(hq,(-1*(e-1),i+u,j+v))    #更新したところの接続点は短くなる可能性があるので再調査

print("No")

Submission Info

Judge Result