結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー rosso01
提出日時 2022-08-01 05:35:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 493 ms / 1,000 ms
コード長 3,486 bytes
コンパイル時間 222 ms
実行使用メモリ 87,712 KB
スコア 5,401,457
最終ジャッジ日時 2022-08-01 05:35:24
合計ジャッジ時間 17,134 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge16
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""
とりあえずのナイーブ解放
全体を①惑星の訪問順を決める、②ステーションの配置を決めるの２つに分ける
①惑星の訪問順
- ランダムシャッフルで初期解を作る
- ２点swap山登り
②ステーションの配置
- ①で決めた訪問順で実際に通る道からなる集合をつくる
- その集合の中で長さ順にM個の枝を選び、その中点にステーションを配置する
"""

#from heapq import heappush,heappop
from random import shuffle,sample

N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(N)]
alpha = 5

G = [{} for _ in range(N)]
for i in range(N-1):
  x1,y1 = AB[i]
  for j in range(i+1,N):
    x2,y2 = AB[j]
    dist = (x2-x1)**2 + (y2-y1)**2
    dist *= alpha**2
    G[i][j] = G[j][i] = dist
    
# ダイクストラ（惑星専用）
def dijkstra(start = 0, INF=10**20):
    from heapq import heappop, heappush
    d = [INF for i in range(len(G))]
    prev = [-1]*len(G)
    d[start] = 0
    que = []
    heappush(que, (0, start))
    while que:
        d_, v = heappop(que)
        if d[v] < d_: continue
        for u, c in G[v].items():
            if d[u] > d[v] + c:
                d[u] = d[v] + c
                prev[u] = v
                heappush(que, (d[u], u))
    return d,prev
  
# sからtまでの最短経路を復元
def recover_path(s,t):
  prev = PREV[s]
  path = [t]
  while prev[t] != -1:
    t = prev[t]
    path.append(t)
  return path[::-1]

# 道順を与えられたときに距離を返す
def calc_score(path):
  assert len(path) == N+1, "The length of path should be N+1"
  score = 0
  for i in range(N):
    score += D[path[i]][path[i+1]]
  return score
  
D = [[0]*N for _ in range(N)]
PREV = [[-1]*N for _ in range(N)]
for i in range(N):
  D[i],PREV[i] = dijkstra(i)

ans = list(range(1,N))
score = calc_score([0]+ans+[0])

# 初期解
for i in range(100):
  ans2 = ans[:]
  shuffle(ans2)
  score2 = calc_score([0]+ans2+[0])
  
  if score2 < score:
    score = score2
    ans = ans2
    
    #print(score)
    
# 2点swapで山登り
for itr in range(10**5):
  i,j = sample(range(N-1),2)
  ans[i],ans[j] = ans[j],ans[i]
  
  score2 = calc_score([0]+ans+[0])
  
  if score2 < score:
    score = score2
    
  else:
    ans[i],ans[j] = ans[j],ans[i]
    
# ステーションを配置
# 使用する枝のうち長い方から順にM個の中点（だいたい）に置くだけ
used = {}
ans = [0]+ans+[0]
all_path = [ans[0]]
for i in range(N):
  s,t = ans[i],ans[i+1]
  path = recover_path(s,t)
  for j in range(len(path)-1):
    a = path[j]
    b = path[j+1]
    all_path.append(b)
    if a > b:
      a,b = b,a
    if (a,b) not in used:
      used[(a,b)] = 0
      
    used[(a,b)] += 1
    
#print(used)

pairs = list(used.keys())
dists = [D[i][j] for i,j in pairs]

longestM = sorted(zip(dists,pairs),reverse=True)[:M]

#print(longestM)

# ステーションを配置
pos = {}
for _, (i,j) in longestM:
  x1,y1 = AB[i]
  x2,y2 = AB[j]
  pos[(i,j)] = ((x1+x2)//2, (y1+y2)//2, len(pos))
  
#print(pos)
#print(score)
#print(all_path)

ANS = [f"{1} {all_path[0]+1}"]
for i in range(len(all_path)-1):
  a,b = all_path[i],all_path[i+1]
  x,y = a,b
  if x > y:
    x,y = y,x
  if (x,y) in pos:
    z = pos[(x,y)][-1]
    ANS.append(f"{2} {z+1}")
  ANS.append(f"{1} {b+1}")
    
CD = [0]*M
for c,d,z in pos.values():
  CD[z] = (c,d)
  
#print(score)
for c,d in CD:
  print(c,d)
    
print(len(ANS))
print("\n".join(ANS))
0