結果

問題 No.20 砂漠のオアシス
ユーザー rafi2rafi2
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 35 ms
52,736 KB
testcase_01 AC 35 ms
52,480 KB
testcase_02 AC 38 ms
53,760 KB
testcase_03 AC 111 ms
77,268 KB
testcase_04 AC 104 ms
76,416 KB
testcase_05 AC 160 ms
79,004 KB
testcase_06 AC 236 ms
79,488 KB
testcase_07 AC 153 ms
77,612 KB
testcase_08 AC 243 ms
79,848 KB
testcase_09 AC 277 ms
79,748 KB
testcase_10 AC 39 ms
52,608 KB
testcase_11 AC 39 ms
52,352 KB
testcase_12 AC 129 ms
77,440 KB
testcase_13 AC 131 ms
76,996 KB
testcase_14 AC 110 ms
76,552 KB
testcase_15 AC 96 ms
76,800 KB
testcase_16 AC 126 ms
77,756 KB
testcase_17 AC 176 ms
78,252 KB
testcase_18 AC 113 ms
77,436 KB
testcase_19 AC 194 ms
78,420 KB
testcase_20 AC 73 ms
73,600 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()

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

print("NO")
0