結果

問題 No.20 砂漠のオアシス
コンテスト
ユーザー rafi2
提出日時 2023-03-16 21:07:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 277 ms / 5,000 ms
コード長 1,876 bytes
コンパイル時間 288 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 79,848 KB
最終ジャッジ日時 2024-09-18 09:30:50
合計ジャッジ時間 3,742 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

n,V,ox,oy = map(int,input().split())
L = [list(map(int,input().split())) for _ in range(n)]
def Dijkstra(L,r,h,w):#1インデックス
    dy = [1,-1,0,0]
    dx = [0,0,1,-1]
    """
    e:隣接リスト
    （隣接する頂点,重さ）
    ダイクストラ法。
    rから各頂点への最短コスト。
    O(ElogV)
    rはタプル
    """
    import heapq
    cur = [[float('inf')]*(w+1) for _ in range(h+1)]
    cur[r[0]][r[1]] = 0#rが初期位置
    que = []
    """""
    cur は　暫定の距離
    que は　未確定頂点の番号とcur(仮)のセットのタプルのリスト
    """""
    heapq.heappush(que,(0,r))#入れる

    while len(que) != 0:
        c,n = heapq.heappop(que)#未確定頂点のなかの最小値取り出して取得　nが重複している場合も全然ある
        if cur[n[0]][n[1]] < c:#cur のあたいがすでにかくていした頂点の場合（？？？未確定頂点からみたときにcurより小さいなら更新される
            continue
        for i in range(4):
            v = n[0]+dy[i]
            u = n[1]+dx[i]
            if 0<v<=h and 0<u<=w:
                cost = L[v-1][u-1]
            else:
                continue
            if cur[v][u] <= c+cost:#i[0]はノード、i[1]は重み
                continue
            heapq.heappush(que,(c+cost,(v,u)))#入れる そこまでの重みを先頭ということに注意
            cur[v][u] = min(cur[v][u],c+cost)#cur[i[0]] = c+i[1]でよくない？
    return cur

if ox == 0 and oy == 0:
    cur = Dijkstra(L,(1,1),n,n)
    if cur[n][n] < V:
        print("YES")
        exit()
    print("NO")
    exit()

cur1 = Dijkstra(L,(oy,ox),n,n)
now = (V-cur1[1][1]+L[0][0]-L[oy-1][ox-1])*2 - cur1[n][n]

if now > 0:
    print("YES")
    exit()

cur = Dijkstra(L,(1,1),n,n)
if cur[n][n] < V:
    print("YES")
    exit()

print("NO")
0