結果
問題 | No.20 砂漠のオアシス |
ユーザー | takakin |
提出日時 | 2020-05-25 21:36:53 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 344 ms / 5,000 ms |
コード長 | 1,097 bytes |
コンパイル時間 | 84 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 22,964 KB |
最終ジャッジ日時 | 2024-10-13 02:14:13 |
合計ジャッジ時間 | 3,369 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
import sys input=lambda: sys.stdin.readline().rstrip() n,v,ox,oy=map(int,input().split()) L=[[int(i) for i in input().split()] for _ in range(n)] nn=n**2 D=((1,0),(0,1),(-1,0),(0,-1)) edge=[[] for i in range(nn)] for i in range(nn): ix,iy=i//n,i%n for dx,dy in D: if 0<=ix+dx<n and 0<=iy+dy<n: edge[i].append(L[ix+dx][iy+dy]*10**6+(ix+dx)*n+iy+dy) import heapq def dijkstra_heap(s): d=[float("inf")]*nn used=[True]*nn d[s]=0 used[s]=False edgelist=[] for e in edge[s]: heapq.heappush(edgelist,e) while edgelist: minedge=heapq.heappop(edgelist) minedge_cost=minedge//(10**6) minedge_v=minedge%(10**6) if not used[minedge_v]: continue d[minedge_v] = minedge_cost used[minedge_v] = False for e in edge[minedge_v]: e_cost=e//(10**6) e_v=e%(10**6) if used[e_v]: heapq.heappush(edgelist,e+minedge_cost*10**6) return d D1=dijkstra_heap(0) D2=dijkstra_heap((oy-1)*n+ox-1) if D1[-1]<v: print("YES") elif ox*oy!=0 and D1[(oy-1)*n+ox-1]<v and D2[-1]<2*(v-D1[(oy-1)*n+ox-1]): print("YES") else: print("NO")