結果
問題 | No.2179 Planet Traveler |
ユーザー |
![]() |
提出日時 | 2023-01-26 22:00:35 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 882 bytes |
コンパイル時間 | 374 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 126,404 KB |
最終ジャッジ日時 | 2024-06-27 12:59:37 |
合計ジャッジ時間 | 24,245 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 24 WA * 1 TLE * 1 |
ソースコード
from math import ceilfrom heapq import *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 = i#if d > D[u]: continuetmp = max(D[u], b)if D[a] > tmp:D[a] = tmpheappush(q, (D[a], a))#print(D)print(ceil(D[N - 1]))