結果
問題 | No.5007 Steiner Space Travel |
ユーザー | rosso01 |
提出日時 | 2022-08-01 06:48:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 904 ms / 1,000 ms |
コード長 | 3,313 bytes |
コンパイル時間 | 322 ms |
実行使用メモリ | 87,868 KB |
スコア | 6,817,615 |
最終ジャッジ日時 | 2022-08-01 06:49:27 |
合計ジャッジ時間 | 30,025 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
純コード判定しない問題か言語 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 893 ms
86,328 KB |
testcase_01 | AC | 898 ms
86,424 KB |
testcase_02 | AC | 892 ms
86,728 KB |
testcase_03 | AC | 891 ms
87,016 KB |
testcase_04 | AC | 891 ms
86,544 KB |
testcase_05 | AC | 896 ms
86,600 KB |
testcase_06 | AC | 891 ms
87,016 KB |
testcase_07 | AC | 891 ms
86,568 KB |
testcase_08 | AC | 904 ms
86,864 KB |
testcase_09 | AC | 893 ms
86,784 KB |
testcase_10 | AC | 892 ms
86,216 KB |
testcase_11 | AC | 892 ms
87,196 KB |
testcase_12 | AC | 896 ms
87,112 KB |
testcase_13 | AC | 893 ms
86,624 KB |
testcase_14 | AC | 895 ms
86,452 KB |
testcase_15 | AC | 901 ms
86,872 KB |
testcase_16 | AC | 892 ms
86,452 KB |
testcase_17 | AC | 892 ms
86,928 KB |
testcase_18 | AC | 893 ms
86,628 KB |
testcase_19 | AC | 897 ms
87,012 KB |
testcase_20 | AC | 892 ms
86,360 KB |
testcase_21 | AC | 899 ms
86,868 KB |
testcase_22 | AC | 902 ms
86,060 KB |
testcase_23 | AC | 893 ms
86,908 KB |
testcase_24 | AC | 893 ms
86,552 KB |
testcase_25 | AC | 892 ms
86,700 KB |
testcase_26 | AC | 891 ms
87,436 KB |
testcase_27 | AC | 891 ms
86,388 KB |
testcase_28 | AC | 892 ms
86,504 KB |
testcase_29 | AC | 904 ms
87,868 KB |
ソースコード
""" 最初の①にかける時間を少なくした。その分、②により多くの時間がさける ①ランダムにステーションを配置して各惑星から最も近いステーションまでのコストの和が最小になる解を山登りで見つける ②次に2点swapでコストの和が最小になる道順を時間いっぱいまで山登りで探索 """ from random import randint,shuffle,sample from time import time # ダイクストラ(惑星専用) 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 stime = time() N,M = map(int,input().split()) AB = [tuple(map(int,input().split())) for _ in range(N)] AB2 = {} for a,b in AB: if a not in AB2: AB2[a] = set() AB2[a].add(b) alpha = 5 res2 = 10**30 argmin = [] for itr in range(1000): CD = [] for i in range(M): c,d = randint(0,999),randint(0,999) while c in AB2 and d in AB2[c]: c,d = randint(0,999),randint(0,999) CD.append((c,d)) res = 0 for a,b in AB: MIN = 10**20 for c,d in CD: MIN = min(MIN,(c-a)**2+(d-b)**2) res += MIN if res < res2: res2 = res argmin = CD CD = argmin G = [{} for _ in range(N+M)] for i in range(N+M-1): if i < N: x1,y1 = AB[i] else: x1,y1 = CD[i-N] for j in range(i+1,N+M): if j < N: x2,y2 = AB[j] else: x2,y2 = CD[j-N] dist = (x2-x1)**2 + (y2-y1)**2 if i<N and j<N: dist *= alpha**2 elif i<N or j<N: dist *= alpha G[i][j] = G[j][i] = dist D = [[0]*(N+M) for _ in range(N+M)] PREV = [[-1]*(N+M) for _ in range(N+M)] for i in range(N+M): 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**7): if time() - stime > 0.8: break 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] 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): all_path.append(path[j+1]) #print(score) #print(all_path) for c,d in CD: print(c,d) print(len(all_path)) for idx in all_path: if idx < N: t = 1 else: t = 2 idx -= N print(t,idx+1)