結果

問題 No.20 砂漠のオアシス
ユーザー rafi2rafi2
提出日時 2023-03-16 21:03:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 192 ms / 5,000 ms
コード長 1,801 bytes
コンパイル時間 345 ms
コンパイル使用メモリ 82,420 KB
実行使用メモリ 79,384 KB
最終ジャッジ日時 2024-12-20 15:14:21
合計ジャッジ時間 3,883 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
53,932 KB
testcase_01 AC 45 ms
54,876 KB
testcase_02 AC 43 ms
54,072 KB
testcase_03 AC 130 ms
77,172 KB
testcase_04 AC 125 ms
76,656 KB
testcase_05 AC 190 ms
79,384 KB
testcase_06 AC 176 ms
77,928 KB
testcase_07 AC 180 ms
77,992 KB
testcase_08 AC 174 ms
78,452 KB
testcase_09 AC 192 ms
78,652 KB
testcase_10 AC 40 ms
53,340 KB
testcase_11 AC 40 ms
53,476 KB
testcase_12 AC 94 ms
76,664 KB
testcase_13 AC 95 ms
76,852 KB
testcase_14 AC 121 ms
76,996 KB
testcase_15 AC 110 ms
76,956 KB
testcase_16 AC 142 ms
77,516 KB
testcase_17 AC 139 ms
77,620 KB
testcase_18 AC 130 ms
77,572 KB
testcase_19 AC 143 ms
77,972 KB
testcase_20 AC 79 ms
73,932 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