結果
問題 | No.2354 Poor Sight in Winter |
ユーザー | AngrySadEight |
提出日時 | 2023-04-04 09:40:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 500 ms / 2,000 ms |
コード長 | 1,462 bytes |
コンパイル時間 | 635 ms |
コンパイル使用メモリ | 81,776 KB |
実行使用メモリ | 101,236 KB |
最終ジャッジ日時 | 2023-10-26 03:06:27 |
合計ジャッジ時間 | 8,029 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
53,468 KB |
testcase_01 | AC | 38 ms
53,468 KB |
testcase_02 | AC | 37 ms
53,468 KB |
testcase_03 | AC | 36 ms
53,468 KB |
testcase_04 | AC | 36 ms
53,468 KB |
testcase_05 | AC | 36 ms
53,468 KB |
testcase_06 | AC | 38 ms
53,468 KB |
testcase_07 | AC | 37 ms
53,468 KB |
testcase_08 | AC | 37 ms
53,468 KB |
testcase_09 | AC | 47 ms
62,160 KB |
testcase_10 | AC | 46 ms
61,992 KB |
testcase_11 | AC | 284 ms
98,616 KB |
testcase_12 | AC | 277 ms
98,412 KB |
testcase_13 | AC | 500 ms
101,236 KB |
testcase_14 | AC | 454 ms
101,032 KB |
testcase_15 | AC | 374 ms
99,400 KB |
testcase_16 | AC | 399 ms
99,640 KB |
testcase_17 | AC | 441 ms
100,004 KB |
testcase_18 | AC | 239 ms
84,508 KB |
testcase_19 | AC | 363 ms
92,060 KB |
testcase_20 | AC | 262 ms
84,952 KB |
testcase_21 | AC | 113 ms
76,576 KB |
testcase_22 | AC | 182 ms
81,032 KB |
testcase_23 | AC | 193 ms
81,188 KB |
testcase_24 | AC | 302 ms
89,552 KB |
testcase_25 | AC | 144 ms
79,116 KB |
testcase_26 | AC | 136 ms
78,264 KB |
testcase_27 | AC | 85 ms
76,268 KB |
testcase_28 | AC | 107 ms
76,472 KB |
ソースコード
import heapq def dijkstra(graph, v, dist, P): hq = [] heapq.heappush(hq, [0, v]) dist[v] = 0 while len(hq) > 0: min_d, cur = heapq.heappop(hq) if dist[cur] != min_d: continue for next_cur, next_d in graph[cur]: if dist[next_cur] > dist[cur] + (next_d + P - 1) // P - 1: dist[next_cur] = dist[cur] + (next_d + P - 1) // P - 1 heapq.heappush(hq, [dist[next_cur], next_cur]) N, K = map(int, input().split()) sx, sy, gx, gy = map(int, input().split()) graph = [[] for _ in range(N + 2)] X = [] Y = [] for i in range(N): x, y = map(int, input().split()) X.append(x) Y.append(y) for i in range(N): for j in range(N): if i != j: graph[i].append([j, abs(X[i] - X[j]) + abs(Y[i] - Y[j])]) for i in range(N): graph[N].append([i, abs(X[i] - sx) + abs(Y[i] - sy)]) graph[i].append([N, abs(X[i] - sx) + abs(Y[i] - sy)]) for i in range(N): graph[N + 1].append([i, abs(X[i] - gx) + abs(Y[i] - gy)]) graph[i].append([N + 1, abs(X[i] - gx) + abs(Y[i] - gy)]) graph[N].append([N + 1, abs(sx - gx) + abs(sy - gy)]) graph[N + 1].append([N, abs(sx - gx) + abs(sy - gy)]) INF = 10 ** 7 ng = 0 ok = 200002 while ok - ng > 1: center = (ok + ng) // 2 dist = [INF for _ in range(N + 2)] dijkstra(graph, N, dist, center) if dist[N + 1] <= K: ok = center else: ng = center #print(ok, ng) print(ok)