結果
問題 | No.2179 Planet Traveler |
ユーザー | Hydru |
提出日時 | 2023-01-06 23:55:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 320 ms / 3,000 ms |
コード長 | 1,284 bytes |
コンパイル時間 | 572 ms |
コンパイル使用メモリ | 87,036 KB |
実行使用メモリ | 157,892 KB |
最終ジャッジ日時 | 2023-08-20 17:31:36 |
合計ジャッジ時間 | 7,562 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 79 ms
71,820 KB |
testcase_01 | AC | 77 ms
71,440 KB |
testcase_02 | AC | 80 ms
71,648 KB |
testcase_03 | AC | 78 ms
71,844 KB |
testcase_04 | AC | 78 ms
71,712 KB |
testcase_05 | AC | 76 ms
72,004 KB |
testcase_06 | AC | 77 ms
71,740 KB |
testcase_07 | AC | 85 ms
76,552 KB |
testcase_08 | AC | 87 ms
77,056 KB |
testcase_09 | AC | 105 ms
77,788 KB |
testcase_10 | AC | 85 ms
76,928 KB |
testcase_11 | AC | 196 ms
109,312 KB |
testcase_12 | AC | 238 ms
108,092 KB |
testcase_13 | AC | 282 ms
126,464 KB |
testcase_14 | AC | 258 ms
157,760 KB |
testcase_15 | AC | 272 ms
157,892 KB |
testcase_16 | AC | 266 ms
157,676 KB |
testcase_17 | AC | 295 ms
123,416 KB |
testcase_18 | AC | 320 ms
124,416 KB |
testcase_19 | AC | 284 ms
124,468 KB |
testcase_20 | AC | 120 ms
84,264 KB |
testcase_21 | AC | 294 ms
120,676 KB |
testcase_22 | AC | 216 ms
102,668 KB |
testcase_23 | AC | 203 ms
97,756 KB |
testcase_24 | AC | 262 ms
112,892 KB |
testcase_25 | AC | 218 ms
103,584 KB |
testcase_26 | AC | 258 ms
116,420 KB |
testcase_27 | AC | 124 ms
84,560 KB |
testcase_28 | AC | 180 ms
93,248 KB |
testcase_29 | AC | 260 ms
109,832 KB |
ソースコード
from math import sqrt from collections import deque n=int(input()) Z=[list(map(int,input().split())) for _ in range(n)] G=[[0 for _ in range(n)] for _ in range(n)] dist=[0] dist_set=set([0]) def max_sqrt(a): l=1 r=int(sqrt(a)+1) while(r-l>1): mid=(r+l)//2 if(mid**2<=a): l=mid else: r=mid return l for i in range(n-1): for j in range(i+1,n): if i==j: continue if Z[i][2]==Z[j][2]: d=(Z[i][0]-Z[j][0])**2+(Z[i][1]-Z[j][1])**2 else: d1=Z[i][0]**2+Z[i][1]**2 d2=Z[j][0]**2+Z[j][1]**2 d=d1+d2-max_sqrt(4*d1*d2) G[i][j]=d G[j][i]=d if d not in dist_set: dist.append(d) dist_set.add(d) def dfs(G,d): not_visit=set([i for i in range(1,n)]) Q=deque() Q.append(0) while(Q): v=Q.pop() visit=set() for i in not_visit: if G[v][i]<=d: visit.add(i) Q.append(i) if i==n-1: return True not_visit-=visit return False dist.sort() l=-1 r=len(dist)-1 while(r-l>1): mid=(r+l)//2 if(dfs(G,dist[mid])): r=mid else: l=mid print(dist[r])