結果

問題 No.2955 Pizza Delivery Plan
ユーザー 👑 p-adicp-adic
提出日時 2024-10-24 17:20:18
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 612 bytes
コンパイル時間 320 ms
コンパイル使用メモリ 82,136 KB
実行使用メモリ 138,944 KB
最終ジャッジ日時 2024-10-25 19:25:13
合計ジャッジ時間 25,511 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
53,620 KB
testcase_01 AC 36 ms
53,472 KB
testcase_02 AC 38 ms
53,680 KB
testcase_03 AC 45 ms
60,744 KB
testcase_04 AC 54 ms
65,824 KB
testcase_05 AC 38 ms
53,264 KB
testcase_06 AC 41 ms
53,808 KB
testcase_07 AC 37 ms
53,204 KB
testcase_08 AC 282 ms
101,400 KB
testcase_09 AC 278 ms
101,292 KB
testcase_10 AC 392 ms
104,788 KB
testcase_11 AC 461 ms
108,740 KB
testcase_12 AC 519 ms
111,796 KB
testcase_13 AC 590 ms
115,736 KB
testcase_14 AC 714 ms
119,404 KB
testcase_15 AC 743 ms
123,124 KB
testcase_16 AC 872 ms
125,192 KB
testcase_17 AC 1,023 ms
128,228 KB
testcase_18 AC 1,188 ms
130,460 KB
testcase_19 AC 1,330 ms
132,396 KB
testcase_20 AC 1,594 ms
134,312 KB
testcase_21 AC 1,797 ms
136,824 KB
testcase_22 AC 1,915 ms
138,944 KB
testcase_23 AC 1,953 ms
138,816 KB
testcase_24 TLE -
testcase_25 AC 523 ms
112,056 KB
testcase_26 AC 463 ms
108,996 KB
testcase_27 AC 405 ms
104,872 KB
testcase_28 AC 1,374 ms
130,336 KB
testcase_29 AC 1,457 ms
132,404 KB
testcase_30 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

R=range
J=lambda:map(int,input().split())
N,K=J()
v=[list(J())for i in R(N)]+[[0,0]]
M=N+1
w=[[9**20]*M for i in R(M)]
for i in R(M):
	for j in R(i,M):w[i][j]=w[j][i]=((v[i][0]-v[j][0])**2+(v[i][1]-v[j][1])**2)**0.5
S=R(1<<N)
D=[[[9**30]*(K+1)for i in R(M)]for p in S]
D[0][N][K]=0
for p in S:
	for i in R(N):
		if(p>>i)&1<1:continue
		q=p^(1<<i);D[p][i][K-1]=D[q][N][K]+w[N][i]
		for j in R(N):
			if(q>>j)&1<1:continue
			for k in R(K):D[p][i][k]=min(D[p][i][k],D[q][j][k+1]+w[j][i])
	for j in R(N):
		if(p>>j)&1<1:continue
		for k in R(K):D[p][N][K]=min(D[p][N][K],D[p][j][k]+w[j][N])
print(D[(1<<N)-1][N][K])
0