#532740 (cLay) No.134 走れ！サブロー君

• 問題: No.134 走れ！サブロー君
• ユーザー: yuruhiya
• 提出日時: 2020-08-18 15:43:41
• 言語: cLay (20240104-1)
• 結果: AC
• 実行時間: 7 ms / 5,000 ms
• コード長: 768 bytes
• コンパイル時間: 2,404 ms
• コンパイル使用メモリ: 166,448 KB
• 実行使用メモリ: 4,524 KB
• 最終ジャッジ日時: 2023-09-19 01:01:37
• 合計ジャッジ時間: 3,077 ms
• ジャッジサーバーID （参考情報）: judge11 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,376 KB
testcase_01	AC	1 ms; 4,380 KB
testcase_02	AC	2 ms; 4,380 KB
testcase_03	AC	2 ms; 4,380 KB
testcase_04	AC	2 ms; 4,380 KB
testcase_05	AC	2 ms; 4,380 KB
testcase_06	AC	3 ms; 4,380 KB
testcase_07	AC	4 ms; 4,380 KB
testcase_08	AC	7 ms; 4,524 KB
testcase_09	AC	7 ms; 4,504 KB
testcase_10	AC	1 ms; 4,376 KB
testcase_11	AC	1 ms; 4,380 KB
testcase_12	AC	2 ms; 4,388 KB
testcase_13	AC	2 ms; 4,376 KB
testcase_14	AC	1 ms; 4,380 KB

ソースコード

int n, m, x[14], y[14], p, q;
double w[13], dp[1 << 13][13];
double dist(int i, int j) {
	return abs(x[i] - x[j]) + abs(y[i] - y[j]);
}
template <class T> void chmin(T& x, const T& v) {
	if (x > v) x = v;
}
{
	rd(p, q, n, (x, y, w)(n));
	m = 1 << n;
	x[n] = p;
	y[n] = q;
	double w_sum = sum(w(n)), k = (w_sum + 100) / 120;
	rep(i, m) rep(j, n) dp[i][j] = ll_inf;
	rep(i, n) {
		dp[0][i] = 0;
		dp[1 << i][i] = dist(i, n) * k + w[i];
	}
	rep(s, m) {
		k = 0;
		rep(v, n) if (!(s & 1 << v)) k += w[v];
		k = (k + 100) / 120;
		rep(v, n) if (s & 1 << v) {
			rep(u, n) if (!(s & 1 << u)) {
				chmin(dp[s | 1 << u][u], dp[s][v] + dist(v, u) * k + w[u]);
			}
		}
	}

	double ans = ll_inf;
	k = 5.0 / 6.0;
	rep(v, n) chmin(ans, dp[m - 1][v] + k * dist(v, n));
	wt(ans);
}