結果

問題 No.20 砂漠のオアシス
ユーザー rafi2rafi2
提出日時 2023-03-16 21:03:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 194 ms / 5,000 ms
コード長 1,801 bytes
コンパイル時間 672 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 78,888 KB
最終ジャッジ日時 2023-10-18 13:12:00
合計ジャッジ時間 3,620 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,416 KB
testcase_01 AC 41 ms
53,416 KB
testcase_02 AC 41 ms
53,416 KB
testcase_03 AC 127 ms
76,896 KB
testcase_04 AC 124 ms
76,292 KB
testcase_05 AC 189 ms
78,888 KB
testcase_06 AC 175 ms
77,404 KB
testcase_07 AC 176 ms
77,640 KB
testcase_08 AC 177 ms
77,616 KB
testcase_09 AC 194 ms
77,864 KB
testcase_10 AC 40 ms
53,488 KB
testcase_11 AC 40 ms
53,488 KB
testcase_12 AC 99 ms
76,092 KB
testcase_13 AC 99 ms
76,188 KB
testcase_14 AC 120 ms
76,360 KB
testcase_15 AC 109 ms
76,160 KB
testcase_16 AC 141 ms
77,104 KB
testcase_17 AC 144 ms
77,156 KB
testcase_18 AC 130 ms
77,164 KB
testcase_19 AC 148 ms
77,248 KB
testcase_20 AC 80 ms
73,420 KB
権限があれば一括ダウンロードができます

ソースコード

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()

print("NO")
0