結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー brthyyjp
提出日時 2023-04-24 23:21:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 981 ms / 1,000 ms
コード長 2,881 bytes
コンパイル時間 359 ms
コンパイル使用メモリ 86,944 KB
実行使用メモリ 80,052 KB
スコア 6,908,974
最終ジャッジ日時 2023-04-24 23:21:53
合計ジャッジ時間 32,560 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

from time import time
start_time = time()

import sys
import io
import os
input = sys.stdin.readline

import random, math

random.seed(42)
alpha = 5
mx = 1000
INF = float('inf')
Ts = 50
Te = 10
TIME_LIMIT = 0.9

limit = 700

n, m = map(int, input().split())
XY = []
for i in range(n):
    x, y = map(int, input().split())
    XY.append((x, y))

CD = []
for i in range(m):
    c = random.randint(0, mx)
    d = random.randint(0, mx)
    CD.append((c, d))

XY += CD

def calc_energy(i, j):
    xi, yi = XY[i]
    xj, yj = XY[j]
    d2 = (xi-xj)**2+(yi-yj)**2
    if 0 <= i < n and 0 <= j < n:    
        return (alpha**2)*d2
    elif n <= i < n+m and n <= j < n+m:
        return d2
    else:
        return alpha*d2

g = [[] for i in range(n+m)]
dist_table = [[INF]*(n+m) for i in range(n+m)]
for i in range(n+m):
    for j in range(n+m):
        if i == j:
            continue
        x1, y1 = XY[j]
        dist =  calc_energy(i, j)
        g[i].append((dist, j))
        dist_table[i][j] = dist


def calc_dist(path, dist_table):
    res = 0
    for v, nv in zip(path, path[1:]):
        res += dist_table[v][nv]
    return res

def nearest_neighbor(s, g):
    n = len(g)
    nonvisit = set(range(n))
    path = []
    path.append(s)
    nonvisit.remove(s)
    while nonvisit:
        min_dist = INF
        nx = -1
        for d, v in g[path[-1]]:
            if not v in nonvisit:
                continue
            if d < min_dist:
                min_dist = d
                nx = v
        path.append(nx)
        nonvisit.remove(nx)
    return path+[s]


def two_opt_with_annealing(path, dist_table, Ts, Te, time_limit):
    n = len(path)
    while True:
        now_time = time()
        if now_time - start_time > time_limit:
            return path
        for i in range(n-3):
            p1 = path[i]
            p2 = path[i+1]
            p_dist = dist_table[p1][p2]
            for j in range(i+2, n-1):
                q1 = path[j]
                q2 = path[j+1]
                q_dist = dist_table[q1][q2]
                cur_dist = p_dist + q_dist
                new_dist = dist_table[p1][q1]+dist_table[p2][q2]
                diff = new_dist-cur_dist
                temp = Ts+(Te-Ts)*(time()-start_time)/time_limit
                prob = math.exp(min(limit, -diff / temp))
                if prob > random.random():
                    sep1, sep2, sep3 = path[:i+1], path[i+1:j+1], path[j+1:]
                    sep2.reverse()
                    path = sep1+sep2+sep3

path = nearest_neighbor(0, g)
path = two_opt_with_annealing(path, dist_table, Ts, Te, TIME_LIMIT)

s = calc_dist(path, dist_table)
score = round(10**9/(1000+math.sqrt(s)))
print(score, file=sys.stderr, flush=True)

for c, d in CD:
    print(c, d)

print(len(path))
for k in range(len(path)):
    r = path[k]
    if 0 <= r < n:
        print(1, r+1)
    else:
        print(2, r-n+1)
0