結果
問題 | No.2354 Poor Sight in Winter |
ユーザー |
![]() |
提出日時 | 2023-06-16 22:42:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,505 ms / 2,000 ms |
コード長 | 1,586 bytes |
コンパイル時間 | 484 ms |
コンパイル使用メモリ | 82,144 KB |
実行使用メモリ | 231,688 KB |
最終ジャッジ日時 | 2024-06-24 15:30:05 |
合計ジャッジ時間 | 13,849 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
import heapq def dijkstra(size,cost,start):#startが(0,0)になってるので、適宜変更して入力にも足す dist=[float("inf")]*size #dist[i]=0からiまでの最短距離 dist[start]=0 h=[]#(0からの暫定距離, 点の番号)というタプルを入れていくheap heapq.heappush(h,(0,start)) while len(h)!=0: now=heapq.heappop(h) for tup in cost[now[1]]: if dist[now[1]]+tup[1]<dist[tup[0]]: dist[tup[0]]=dist[now[1]]+tup[1] heapq.heappush(h,(dist[tup[0]],tup[0])) return dist def dist0(tup1,tup2): return abs(tup1[0]-tup2[0])+abs(tup1[1]-tup2[1]) N,K=map(int,input().split()) sx,sy,gx,gy=map(int,input().split()) ok=3*10**5 ng=0 ji=[tuple(map(int,input().split())) for _ in range(N)] while ok-ng>1: #print(ok,ng) now=(ok+ng)//2 graph=[[] for _ in range(N+2)] graph[N].append((N+1,(dist0((sx,sy),(gx,gy))+now-1)//now-1)) graph[N+1].append((N,(dist0((sx,sy),(gx,gy))+now-1)//now-1)) for i in range(N): graph[i].append((N,(dist0((sx,sy),ji[i])+now-1)//now-1)) graph[N].append((i,(dist0((sx,sy),ji[i])+now-1)//now-1)) graph[i].append((N+1,(dist0((gx,gy),ji[i])+now-1)//now-1)) graph[N+1].append((i,(dist0((gx,gy),ji[i])+now-1)//now-1)) for i in range(N-1): for j in range(i+1,N): graph[i].append((j,(dist0(ji[j],ji[i])+now-1)//now-1)) graph[j].append((i,(dist0(ji[j],ji[i])+now-1)//now-1)) dist=dijkstra(N+2,graph,N) if dist[N+1]<=K: ok=now else: ng=now print(ok)