結果
問題 | No.20 砂漠のオアシス |
ユーザー | rafi2 |
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
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 heapqcur = [[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より小さいなら更新されるcontinuefor 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:continueif cur[v][u] <= c+cost:#i[0]はノード、i[1]は重みcontinueheapq.heappush(que,(c+cost,(v,u)))#入れる そこまでの重みを先頭ということに注意cur[v][u] = min(cur[v][u],c+cost)#cur[i[0]] = c+i[1]でよくない?return curif 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")