結果
問題 |
No.168 ものさし
|
ユーザー |
![]() |
提出日時 | 2020-12-13 13:13:24 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 986 bytes |
コンパイル時間 | 146 ms |
コンパイル使用メモリ | 81,948 KB |
実行使用メモリ | 84,452 KB |
最終ジャッジ日時 | 2024-09-19 23:27:31 |
合計ジャッジ時間 | 2,341 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 19 |
ソースコード
def Prim_dense(g): n = len(g) INF = 2*10**18 + 5 smallest = [INF]*n # 頂点 i から到達できる使用済みの点までの距離の最小値 smallest[0] = 0 used = [0]*n ans = 0 for i in range(n): v = -1 d = INF for j in range(n): if used[j]==0 and smallest[j] < d: v = j d = smallest[j] ans = max(ans,d) if v==-1: #非連結 return None break if v==n-1: return ans used[v] = 1 for j in range(n): if used[j]==0 and smallest[j] > g[v][j]: smallest[j] = g[v][j] #return sum(smallest) return smallest[-1] n = int(input()) xy = [list(map(int,input().split())) for _ in range(n)] g = [[(xi-xj)**2+(yi-yj)**2 for xj,yj in xy] for xi,yi in xy] d = Prim_dense(g) r = int(d**0.5) v = max(0,(r-3)//10*10) for i in range(v,v+100,10): if i*i >= d: print(i) break