結果
問題 | No.2354 Poor Sight in Winter |
ユーザー | chankei271828 |
提出日時 | 2023-06-16 22:42:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,541 ms / 2,000 ms |
コード長 | 1,586 bytes |
コンパイル時間 | 443 ms |
コンパイル使用メモリ | 86,868 KB |
実行使用メモリ | 232,392 KB |
最終ジャッジ日時 | 2023-09-06 21:09:08 |
合計ジャッジ時間 | 15,231 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 78 ms
71,248 KB |
testcase_01 | AC | 78 ms
71,384 KB |
testcase_02 | AC | 79 ms
71,392 KB |
testcase_03 | AC | 78 ms
71,196 KB |
testcase_04 | AC | 80 ms
71,044 KB |
testcase_05 | AC | 79 ms
71,384 KB |
testcase_06 | AC | 79 ms
71,036 KB |
testcase_07 | AC | 78 ms
71,420 KB |
testcase_08 | AC | 76 ms
71,036 KB |
testcase_09 | AC | 99 ms
76,236 KB |
testcase_10 | AC | 90 ms
76,244 KB |
testcase_11 | AC | 761 ms
226,380 KB |
testcase_12 | AC | 813 ms
223,992 KB |
testcase_13 | AC | 1,185 ms
230,524 KB |
testcase_14 | AC | 1,541 ms
228,884 KB |
testcase_15 | AC | 1,116 ms
228,012 KB |
testcase_16 | AC | 1,285 ms
232,392 KB |
testcase_17 | AC | 1,102 ms
231,872 KB |
testcase_18 | AC | 538 ms
110,728 KB |
testcase_19 | AC | 860 ms
176,600 KB |
testcase_20 | AC | 644 ms
117,940 KB |
testcase_21 | AC | 255 ms
81,108 KB |
testcase_22 | AC | 463 ms
93,612 KB |
testcase_23 | AC | 420 ms
93,948 KB |
testcase_24 | AC | 714 ms
150,812 KB |
testcase_25 | AC | 310 ms
85,412 KB |
testcase_26 | AC | 285 ms
83,068 KB |
testcase_27 | AC | 157 ms
78,992 KB |
testcase_28 | AC | 207 ms
80,212 KB |
ソースコード
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)