結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
|
提出日時 | 2022-07-30 14:23:09 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 30 ms / 1,000 ms |
コード長 | 915 bytes |
コンパイル時間 | 273 ms |
実行使用メモリ | 8,388 KB |
スコア | 4,521,707 |
最終ジャッジ日時 | 2022-07-30 14:23:12 |
合計ジャッジ時間 | 2,619 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge10 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
def greedy(cities,current_city,dist): N = len(cities) unvisited_cities = set(range(0, N)) tour = [current_city] unvisited_cities.remove(current_city) while unvisited_cities: next_city = min(unvisited_cities, key=lambda city: dist[current_city][city]) unvisited_cities.remove(next_city) tour.append(next_city) current_city = next_city return tour,dist # ==================== N, M = map(int, input().split()) planet = [tuple(map(int, input().split())) for _ in range(N)] dist = [[0 for _ in range(N)] for _ in range(N)] for i in range(N): for j in range(N): p1 = planet[i] p2 = planet[j] D = (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2 dist[i][j] = D tour, dis = greedy(planet, 0, dist) for _ in range(M):print(*planet[0]) print(len(tour)+1) for i in range(len(tour)):print(1, tour[i]+1) print(1, 1)