#1025122 (C) No.2955 Pizza Delivery Plan

• 問題: No.2955 Pizza Delivery Plan
• ユーザー: ygussany
• 提出日時: 2024-11-08 22:03:44
• 言語: C (gcc 12.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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	0 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	1 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	26 ms; 30,592 KB
testcase_09	AC	41 ms; 30,592 KB
testcase_10	AC	31 ms; 30,592 KB
testcase_11	AC	40 ms; 30,592 KB
testcase_12	AC	38 ms; 30,592 KB
testcase_13	AC	40 ms; 30,592 KB
testcase_14	AC	45 ms; 30,592 KB
testcase_15	AC	50 ms; 30,592 KB
testcase_16	AC	49 ms; 30,592 KB
testcase_17	AC	54 ms; 30,592 KB
testcase_18	AC	57 ms; 30,592 KB
testcase_19	AC	59 ms; 30,592 KB
testcase_20	AC	64 ms; 30,592 KB
testcase_21	AC	68 ms; 30,592 KB
testcase_22	AC	69 ms; 30,592 KB
testcase_23	AC	68 ms; 30,592 KB
testcase_24	AC	72 ms; 30,592 KB
testcase_25	AC	36 ms; 30,592 KB
testcase_26	AC	31 ms; 30,592 KB
testcase_27	AC	27 ms; 30,592 KB
testcase_28	AC	56 ms; 30,592 KB
testcase_29	AC	59 ms; 30,592 KB
testcase_30	AC	70 ms; 30,592 KB

コンパイルメッセージ

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'

ソースコード

#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;
}