結果
問題 | 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_cityreturn 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]) ** 2dist[i][j] = Dtour, 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)