結果
問題 | No.20 砂漠のオアシス |
ユーザー | square1001 |
提出日時 | 2022-02-17 15:00:42 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 331 ms / 5,000 ms |
コード長 | 921 bytes |
コンパイル時間 | 110 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 13,696 KB |
最終ジャッジ日時 | 2024-06-29 07:41:25 |
合計ジャッジ時間 | 2,612 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
import heapq # Input N, V, OY, OX = map(int, input().split()) L = [ list(map(int, input().split())) for i in range(N) ] OX, OY = OX - 1, OY - 1 # Dijkstra dx = [ 0, 1, 0, -1 ] dy = [ 1, 0, -1, 0 ] dist = [ [ [ 0 ] * N for j in range(N) ] for i in range(2) ] vis = [ [ [ False ] * N for j in range(N) ] for i in range(2) ] que = [ (-V, 0, 0, 0) ] heapq.heapify(que) dist[0][0][0] = V while len(que) >= 1: u = heapq.heappop(que) if vis[u[1]][u[2]][u[3]]: continue vis[u[1]][u[2]][u[3]] = True for i in range(4): tx, ty = u[2] + dx[i], u[3] + dy[i] if 0 <= tx and tx < N and 0 <= ty and ty < N: ncost = -u[0] - L[tx][ty] tc = u[1] if tc == 0 and tx == OX and ty == OY: ncost *= 2 tc = 1 if dist[tc][tx][ty] < ncost: dist[tc][tx][ty] = ncost heapq.heappush(que, (-ncost, tc, tx, ty)) # Output if dist[0][N - 1][N - 1] > 0 or dist[1][N - 1][N - 1] > 0: print("YES") else: print("NO")