結果
問題 | No.20 砂漠のオアシス |
ユーザー | ntuda |
提出日時 | 2024-11-04 22:33:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 318 ms / 5,000 ms |
コード長 | 1,032 bytes |
コンパイル時間 | 347 ms |
コンパイル使用メモリ | 82,352 KB |
実行使用メモリ | 82,444 KB |
最終ジャッジ日時 | 2024-11-04 22:33:41 |
合計ジャッジ時間 | 4,663 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
from heapq import * N,V,OY,OX = map(int,input().split()) L= [list(map(int,input().split())) for _ in range(N)] OX -= 1 OY -= 1 start = (0,0) goal = (N-1,N-1) oasys = (OX,OY) INF = 10 ** 6 dir = [[1, 0], [0, 1], [0, -1], [-1, 0]] def dijkstra(B,E): M = [[INF] * N for _ in range(N)] M[B[0]][B[1]] = 0 Q = [(0,B)] while Q: d, (x, y) = heappop(Q) #if M[x][y] > d: # continue for xd, yd in dir: x1 = x + xd y1 = y + yd if 0 <= x1 < N and 0 <= y1 < N: d2 = d + L[x1][y1] if M[x1][y1] > d2: M[x1][y1] = d2 if (x1,y1) == E: return M[x1][y1] heappush(Q,(d2,(x1, y1))) return INF if dijkstra(start,goal) < V: print("YES") else: a = dijkstra(start,oasys) if a >= V: print("NO") else: b = dijkstra(oasys,goal) if b < 2 * (V - a): print("YES") else: print("NO")