結果
問題 |
No.5007 Steiner Space Travel
|
ユーザー |
|
提出日時 | 2022-10-11 16:51:00 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 725 bytes |
コンパイル時間 | 860 ms |
実行使用メモリ | 86,804 KB |
スコア | 0 |
最終ジャッジ日時 | 2022-10-11 16:51:20 |
合計ジャッジ時間 | 17,943 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | RE * 30 |
ソースコード
import sys import random import time import math from a import TSP from kmeans import KmeansPlusPlus N, M = map(int, input().split()) AB = [tuple(map(int, input().split())) for _ in range(N)] kmeans = KmeansPlusPlus(M) labels, cluster_centers = kmeans.fit(AB) obj = AB + cluster_centers dist = [[0]*(N+M) for _ in range(N+M)] for i in range(N+M): for j in range(N+M): d = (obj[i][0] - obj[j][0])**2 + (obj[i][1] - obj[j][1])**2 if i < N: d *= 5 if j < N: d *= 5 dist[i][j] = 5 tsp = TSP(obj) path, score, loops = tsp.solve() print(score, file=sys.stderr) for c,d in cluster_centers: print(c, d) print(len(path)) for p in path: if p < N: print(1, p+1) else: print(2, p-N+1)