結果

問題 No.5007 Steiner Space Travel
ユーザー terry_u16terry_u16
提出日時 2022-06-30 02:18:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 98 ms / 1,000 ms
コード長 2,122 bytes
コンパイル時間 255 ms
実行使用メモリ 80,800 KB
スコア 4,521,707
最終ジャッジ日時 2022-07-30 13:31:55
合計ジャッジ時間 4,594 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 98 ms
80,548 KB
testcase_01 AC 97 ms
80,452 KB
testcase_02 AC 93 ms
80,532 KB
testcase_03 AC 89 ms
80,496 KB
testcase_04 AC 91 ms
80,764 KB
testcase_05 AC 90 ms
80,488 KB
testcase_06 AC 88 ms
80,496 KB
testcase_07 AC 91 ms
80,608 KB
testcase_08 AC 97 ms
80,488 KB
testcase_09 AC 93 ms
80,368 KB
testcase_10 AC 92 ms
80,604 KB
testcase_11 AC 93 ms
80,536 KB
testcase_12 AC 93 ms
80,676 KB
testcase_13 AC 93 ms
80,640 KB
testcase_14 AC 92 ms
80,600 KB
testcase_15 AC 93 ms
80,496 KB
testcase_16 AC 93 ms
80,616 KB
testcase_17 AC 90 ms
80,632 KB
testcase_18 AC 90 ms
80,600 KB
testcase_19 AC 89 ms
80,672 KB
testcase_20 AC 92 ms
80,416 KB
testcase_21 AC 92 ms
80,552 KB
testcase_22 AC 91 ms
80,636 KB
testcase_23 AC 89 ms
80,672 KB
testcase_24 AC 92 ms
80,608 KB
testcase_25 AC 93 ms
80,692 KB
testcase_26 AC 90 ms
80,608 KB
testcase_27 AC 92 ms
80,492 KB
testcase_28 AC 89 ms
80,800 KB
testcase_29 AC 95 ms
80,688 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

INF = 1000000000

# ========================
#       入力読み込み
# ========================
n, m = map(int, input().split())

# 各経由地の座標
points = []

for _ in range(n):
    x, y = map(int, input().split())
    points.append((x, y))

# 宇宙ステーションの座標は適当に決め打ち
#
#   x  x  x
#   x     x
#   x  x  x
#
# みたいにする
points.append((300, 300))
points.append((300, 500))
points.append((300, 700))
points.append((500, 300))
points.append((500, 700))
points.append((700, 300))
points.append((700, 500))
points.append((700, 700))


# ========================
#      エネルギー計算
# ========================


def calc_energy(i, j):
    """
    2点間の消費エネルギーを計算する関数
    """
    x1, y1 = points[i]
    x2, y2 = points[j]
    dx = x1 - x2
    dy = y1 - y2
    energy = dx * dx + dy * dy

    # 惑星かどうかは i < n で判定可能
    if i < n:
        energy *= 5
    if j < n:
        energy *= 5
    return energy


# ========================
#    経路の作成（貪欲法）
# ========================


# 惑星1から出発し、一番近い惑星を貪欲に選び続ける（Nearest Neighbour法）
v = 0
visited = [False] * n
visited[0] = True
route = [0]

# 惑星1以外のN-1個の惑星を訪問していく
for _ in range(n - 1):
    nearest_dist = INF
    nearest_v = -1

    # 一番近い惑星を探す
    for next in range(n):
        if visited[next]:
            continue

        d = calc_energy(v, next)
        if d < nearest_dist:
            nearest_dist = d
            nearest_v = next

    # 次の頂点に移動
    v = nearest_v
    visited[v] = True
    route.append(nearest_v)

# 最後に惑星1に戻る必要がある
route.append(0)


# ========================
#         解の出力
# ========================


# 宇宙ステーションの座標を出力
for x, y in points[n:]:
    print(f"{x} {y}")

# 経路の長さを出力
print(len(route))

# 経路を出力
for v in route:
    if v < n:
        print(f"1 {v + 1}")
    else:
        print(f"2 {v - n + 1}")
0