結果
問題 | No.2179 Planet Traveler |
ユーザー |
![]() |
提出日時 | 2023-01-26 22:13:36 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 944 bytes |
コンパイル時間 | 141 ms |
コンパイル使用メモリ | 82,544 KB |
実行使用メモリ | 126,772 KB |
最終ジャッジ日時 | 2024-06-27 13:06:54 |
合計ジャッジ時間 | 19,000 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 4 |
other | WA * 26 |
ソースコード
from math import ceilfrom heapq import *import timest = time.time()N = int(input())RXYT = []for i in range(N):x, y, t = map(int, input().split())r = (x ** 2 + y ** 2) ** 0.5RXYT.append((r, x, y, t))E = [[] for _ in range(N)]for i in range(N - 1):r1, x1, y1, t1 = RXYT[i]for j in range(i + 1, N):r2, x2, y2, t2 = RXYT[j]if t1 == t2:tmp = (x1 - x2) ** 2 + (y1 - y2) ** 2E[i].append((j, tmp))E[j].append((i, tmp))else:tmp = (r1 - r2) ** 2E[i].append((j, tmp))E[j].append((i, tmp))D = [float('inf')] * ND[0] = 0q = [(0, 0)]while len(q) > 0:d, u = heappop(q)for i in E[u]:a, b = iif d > D[u]: continuetmp = max(D[u], b)if D[a] > tmp:D[a] = tmpheappush(q, (D[a], a))#print(D)print(ceil(round(D[N - 1],8)))print(time.time() - st)