結果
問題 | No.134 走れ!サブロー君 |
ユーザー |
![]() |
提出日時 | 2020-08-18 14:28:31 |
言語 | cLay (20241019-1) |
結果 |
WA
|
実行時間 | - |
コード長 | 645 bytes |
コンパイル時間 | 2,387 ms |
コンパイル使用メモリ | 176,300 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-05 13:53:56 |
合計ジャッジ時間 | 3,034 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 9 WA * 6 |
ソースコード
int n, m, x[15], y[15], p, q;double w[15], dp[1 << 15][15], ww[1 << 15];double calc(int i, int j, double weight) {return (weight + 100.0) / 120.0 * (abs(x[i] - x[j]) + abs(y[i] - y[j]));}{rd(p, q, n, (x, y, w)(n));x[n] = p;y[n] = q;m = 1 << n;double sum_w = sum(w(n));rep(i, m) rep(j, n) dp[i][j] = ll_inf;rep(v, n) dp[m - 1][v] = calc(v, n, 0);ww[m - 1] = sum_w;rrep(s, m - 1) {rep(v, n) rep(u, n) {if (!(s & 1 << u)) {ww[s] = ww[s | 1 << u] - w[u];dp[s][v] <?= dp[s | 1 << u][u] + calc(v, u, ww[s]);}}}double ans = ll_inf;rep(i, n) ans <?= dp[0][i] + calc(i, n, sum_w);wt(ans + sum_w);}