結果

問題 No.5007 Steiner Space Travel
ユーザー MichirakaraMichirakara
提出日時 2023-04-27 14:02:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 310 ms / 1,000 ms
コード長 3,849 bytes
コンパイル時間 1,233 ms
コンパイル使用メモリ 87,092 KB
実行使用メモリ 80,360 KB
スコア 7,620,588
最終ジャッジ日時 2023-04-27 14:03:10
合計ジャッジ時間 11,925 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 276 ms
79,320 KB
testcase_01 AC 269 ms
79,536 KB
testcase_02 AC 268 ms
79,840 KB
testcase_03 AC 277 ms
79,868 KB
testcase_04 AC 287 ms
79,300 KB
testcase_05 AC 292 ms
79,548 KB
testcase_06 AC 280 ms
80,112 KB
testcase_07 AC 273 ms
79,876 KB
testcase_08 AC 283 ms
79,592 KB
testcase_09 AC 279 ms
79,784 KB
testcase_10 AC 275 ms
79,652 KB
testcase_11 AC 297 ms
80,048 KB
testcase_12 AC 310 ms
79,868 KB
testcase_13 AC 281 ms
79,972 KB
testcase_14 AC 271 ms
79,764 KB
testcase_15 AC 292 ms
79,300 KB
testcase_16 AC 262 ms
79,456 KB
testcase_17 AC 264 ms
80,108 KB
testcase_18 AC 263 ms
79,600 KB
testcase_19 AC 300 ms
79,716 KB
testcase_20 AC 275 ms
79,064 KB
testcase_21 AC 271 ms
80,360 KB
testcase_22 AC 279 ms
79,776 KB
testcase_23 AC 268 ms
79,444 KB
testcase_24 AC 296 ms
79,884 KB
testcase_25 AC 284 ms
79,876 KB
testcase_26 AC 284 ms
79,096 KB
testcase_27 AC 291 ms
79,964 KB
testcase_28 AC 274 ms
80,300 KB
testcase_29 AC 258 ms
79,340 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


distances = [[0] * len(points) for _ in range(len(points))]

# 全点間エネルギーを計算
for i in range(len(points)):
    for j in range(len(points)):
        distances[i][j] = calc_energy(i, j)

# ワーシャルフロイド
for k in range(len(points)):
    for i in range(len(points)):
        for j in range(len(points)):
            d = distances[i][k] + distances[k][j]
            distances[i][j] = min(distances[i][j], d)


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


def dijkstra(i, j):
    """
    ダイクストラを行い、経由点iから経由点jへの最短経路を復元する関数
    """
    dijkstra_dist = [INF for _ in range(len(points))]

    # 1つ前にいた頂点を保存する配列（経路復元用）
    prev_points = [-1 for _ in range(len(points))]

    # (距離, 頂点)のペアをpush
    queue = [(0, i)]
    dijkstra_dist[i] = 0

    while queue:
        d, v = heapq.heappop(queue)
        if d > dijkstra_dist[v]:
            continue

        for next in range(len(points)):
            next_d = d + calc_energy(v, next)
            if next_d < dijkstra_dist[next]:
                # 1つ前の頂点を保存しておく
                prev_points[next] = v
                dijkstra_dist[next] = next_d
                heapq.heappush(queue, (next_d, next))

    # ここから経路復元
    # ゴールから1つずつ頂点を辿っていく
    # パンくずみたいな感じ
    v = j
    path = []

    # スタートに戻るまでループ
    while v != i:
        path.append(v)
        v = prev_points[v]

    # pathには経路が逆順で入っているのでひっくり返す
    path.reverse()

    return path


# 惑星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

        if distances[v][next] < nearest_dist:
            nearest_dist = distances[v][next]
            nearest_v = next

    # パスを復元
    path = dijkstra(v, nearest_v)
    route.extend(path)

    # 次の頂点に移動
    v = nearest_v
    visited[v] = True

# 最後に惑星1に戻る必要がある
path = dijkstra(v, 0)
route.extend(path)


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


# 宇宙ステーションの座標を出力
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