結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
![]() |
提出日時 | 2024-11-08 22:55:10 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 399 ms / 2,000 ms |
コード長 | 981 bytes |
コンパイル時間 | 223 ms |
コンパイル使用メモリ | 32,744 KB |
実行使用メモリ | 67,456 KB |
最終ジャッジ日時 | 2024-11-08 22:55:34 |
合計ジャッジ時間 | 6,640 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include<stdio.h>#include<math.h>double x[16], y[16];double dist(long long int i, long long int j){return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));}double dp[100005][16][16];int main(){long long int n, k;scanf("%lld %lld", &n, &k);long long int i, j, l, c;for (i = 0; i < n; i++)scanf("%lf%lf", &x[i + 1], &y[i + 1]);x[0] = y[0] = 0;for (i = 0; i < (1 << (n + 1)); i++)for (j = 0; j <= n; j++)for (l = 0; l <= k; l++)dp[i][j][l] = 1e18;dp[1][0][k] = 0;for (l = 0; l < (1 << (n + 1)); l++){for (i = n; i >= 0; i--){for (c = 0; c <= k; c++){dp[l | 1][0][k] = fmin(dp[l | 1][0][k], dp[l][i][c] + dist(0, i));if (c == 0)continue;for (j = 1; j <= n; j++){if (((l >> j) & 1) > 0)continue;dp[l | (1 << j)][j][c - 1] = fmin(dp[l | (1 << j)][j][c - 1], dp[l][i][c] + dist(i, j));}}}}printf("%.20lf\n", dp[(1 << (n + 1)) - 1][0][k]);return 0;}