結果
問題 | No.2354 Poor Sight in Winter |
ユーザー | Nikkuniku029 |
提出日時 | 2023-06-19 19:27:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,362 ms / 2,000 ms |
コード長 | 1,470 bytes |
コンパイル時間 | 1,057 ms |
コンパイル使用メモリ | 86,884 KB |
実行使用メモリ | 233,360 KB |
最終ジャッジ日時 | 2023-09-09 14:54:26 |
合計ジャッジ時間 | 15,410 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,188 KB |
testcase_01 | AC | 72 ms
71,488 KB |
testcase_02 | AC | 72 ms
71,048 KB |
testcase_03 | AC | 72 ms
71,304 KB |
testcase_04 | AC | 72 ms
71,312 KB |
testcase_05 | AC | 72 ms
71,424 KB |
testcase_06 | AC | 74 ms
71,416 KB |
testcase_07 | AC | 74 ms
71,356 KB |
testcase_08 | AC | 75 ms
71,344 KB |
testcase_09 | AC | 86 ms
75,988 KB |
testcase_10 | AC | 91 ms
76,440 KB |
testcase_11 | AC | 646 ms
214,588 KB |
testcase_12 | AC | 613 ms
217,688 KB |
testcase_13 | AC | 1,362 ms
231,804 KB |
testcase_14 | AC | 1,241 ms
233,360 KB |
testcase_15 | AC | 969 ms
218,544 KB |
testcase_16 | AC | 1,183 ms
221,660 KB |
testcase_17 | AC | 1,161 ms
231,352 KB |
testcase_18 | AC | 456 ms
103,172 KB |
testcase_19 | AC | 899 ms
159,196 KB |
testcase_20 | AC | 520 ms
113,808 KB |
testcase_21 | AC | 181 ms
79,060 KB |
testcase_22 | AC | 330 ms
88,808 KB |
testcase_23 | AC | 315 ms
89,256 KB |
testcase_24 | AC | 653 ms
149,856 KB |
testcase_25 | AC | 232 ms
82,340 KB |
testcase_26 | AC | 233 ms
80,708 KB |
testcase_27 | AC | 133 ms
78,172 KB |
testcase_28 | AC | 165 ms
79,096 KB |
ソースコード
from heapq import heappush, heappop def dijkstra(s, n, adj): # (始点, ノード数) INF = 10 ** 9 dist = [INF] * n hq = [(0, s)] # (distance, node) dist[s] = 0 seen = [False] * n # ノードが確定済みかどうか while hq: v = heappop(hq)[1] # ノードを pop する seen[v] = True for to, cost in adj[v]: # ノード v に隣接しているノードに対して if seen[to] == False and dist[v] + cost < dist[to]: dist[to] = dist[v] + cost heappush(hq, (dist[to], to)) return dist N, K = map(int, input().split()) sx, sy, gx, gy = map(int, input().split()) Points = [[sx, sy]] for _ in range(N): Points.append(list(map(int, input().split()))) Points.append([gx, gy]) # 距離配列作成 dist = [[0]*(N+2) for _ in range(N+2)] for i in range(N+2): for j in range(N+2): if i == j: continue D = abs(Points[i][0]-Points[j][0])+abs(Points[i][1]-Points[j][1]) dist[i][j] = D dist[j][i] = D l = 0 r = 2*10**5 + 5 while r-l > 1: Edge = [[] for _ in range(N+2)] mid = (l+r)//2 for i in range(N+2): for j in range(i+1, N+2): p = dist[i][j]//mid if dist[i][j] % mid == 0: p -= 1 Edge[i].append((j, p)) Edge[j].append((i, p)) res = dijkstra(0, N+2, Edge) if res[-1] <= K: r = mid else: l = mid print(r)