結果

問題 No.2955 Pizza Delivery Plan
ユーザー 👑 ygussany
提出日時 2024-11-08 22:03:44
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 72 ms / 2,000 ms
コード長 1,256 bytes
コンパイル時間 206 ms
コンパイル使用メモリ 32,824 KB
実行使用メモリ 30,592 KB
最終ジャッジ日時 2024-11-08 22:03:55
合計ジャッジ時間 2,339 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'distance':
main.c:10:16: warning: implicit declaration of function 'sqrt' [-Wimplicit-function-declaration]
   10 |         return sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y));
      |                ^~~~
main.c:2:1: note: include '<math.h>' or provide a declaration of 'sqrt'
    1 | #include <stdio.h>
  +++ |+#include <math.h>
    2 | 
main.c:10:16: warning: incompatible implicit declaration of built-in function 'sqrt' [-Wbuiltin-declaration-mismatch]
   10 |         return sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y));
      |                ^~~~
main.c:10:16: note: include '<math.h>' or provide a declaration of 'sqrt'

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
typedef struct {
double x, y;
} point;
// The distance between p and q
double distance(point p, point q)
{
return sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y));
}
const int bit[21] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576};
void chmin(double *a, double b)
{
if (*a > b) *a = b;
}
int main()
{
int i, N, K;
point p[15];
scanf("%d %d", &N, &K);
for (i = 0, p[N].x = 0.0, p[N].y = 0.0; i < N; i++) scanf("%lf %lf", &(p[i].x), &(p[i].y));
int j, k, ii;
double dp[16384][15][15], dist[15][15];
const double sup = 1e+16;
for (k = 0; k < bit[N]; k++) for (i = 0; i <= N; i++) for (j = 0; j <= K; j++) dp[k][i][j] = sup;
for (i = 0; i <= N; i++) for (j = 0; j <= N; j++) dist[i][j] = distance(p[i], p[j]);
for (k = 0, dp[0][N][K] = 0.0; k < bit[N]; k++) {
for (i = 0; i <= N; i++) {
chmin(&(dp[k][N][K]), dp[k][i][0] + dist[i][N]);
for (j = 1; j <= K; j++) {
if (dp[k][i][j] == sup) continue;
for (ii = 0; ii < N; ii++) chmin(&(dp[k | bit[ii]][ii][j-1]), dp[k][i][j] + dist[i][ii]);
chmin(&(dp[k][N][K]), dp[k][i][j] + dist[i][N]);
}
}
}
printf("%.7lf\n", dp[bit[N]-1][N][K]);
fflush(stdout);
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0