結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
![]() |
提出日時 | 2024-11-10 21:04:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 961 ms / 2,000 ms |
コード長 | 1,080 bytes |
コンパイル時間 | 339 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 172,672 KB |
最終ジャッジ日時 | 2024-11-10 21:05:17 |
合計ジャッジ時間 | 17,903 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
N, K = map(int, input().split())X, Y = [0] * (N + 1), [0] * (N + 1)for i in range(N):X[i + 1], Y[i + 1] = map(int, input().split())N += 1N2 = 1 << Ninf = 1e18dp = [[[inf] * (K + 1) for _ in range(N)] for _ in range(N2)]dp[1][0][K] = 0def f(x1, y1, x2, y2):return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5for s in range(N2):for i in range(N):if (s >> i) & 1 == 0:continuefor k in range(K + 1):if dp[s][i][k] > inf/2:continuedp[s][0][K] = min(dp[s][0][K], dp[s][i][k] + f(X[0], Y[0], X[i], Y[i]))for i in range(N):if (s >> i) & 1 == 0:continuefor k in range(K + 1):if dp[s][i][k] > inf/2:continueif k == 0:continuefor j in range(N):if (s >> j) & 1:continuens = s | (1 << j)dp[ns][j][k - 1] = min(dp[ns][j][k - 1], dp[s][i][k] + f(X[i], Y[i], X[j], Y[j]))print(dp[-1][0][K])