結果
問題 | No.134 走れ!サブロー君 |
ユーザー | koba-e964 |
提出日時 | 2015-06-06 19:14:21 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 16 ms / 5,000 ms |
コード長 | 1,460 bytes |
コンパイル時間 | 632 ms |
コンパイル使用メモリ | 60,636 KB |
実行使用メモリ | 11,904 KB |
最終ジャッジ日時 | 2024-04-22 18:03:28 |
合計ジャッジ時間 | 1,519 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 8 ms
11,904 KB |
testcase_01 | AC | 8 ms
11,904 KB |
testcase_02 | AC | 8 ms
11,648 KB |
testcase_03 | AC | 8 ms
11,776 KB |
testcase_04 | AC | 8 ms
11,776 KB |
testcase_05 | AC | 8 ms
11,904 KB |
testcase_06 | AC | 10 ms
11,776 KB |
testcase_07 | AC | 11 ms
11,776 KB |
testcase_08 | AC | 16 ms
11,648 KB |
testcase_09 | AC | 15 ms
11,648 KB |
testcase_10 | AC | 8 ms
11,904 KB |
testcase_11 | AC | 8 ms
11,904 KB |
testcase_12 | AC | 8 ms
11,776 KB |
testcase_13 | AC | 8 ms
11,776 KB |
testcase_14 | AC | 8 ms
11,776 KB |
ソースコード
#include <algorithm> #include <cstdio> #include <iostream> #include <vector> #include <cassert> #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) using namespace std; typedef long long int ll; typedef vector<int> VI; typedef pair<int, int> PI; const double EPS=1e-9; const ll inf = 0x3fffffffLL << 31; const int N = 15; int x[N], y[N]; double w[N]; int n; double dp[2 << N][N + 1]; // the shortest path from v to 0 using vertices bits double rec(int bits, int v) { double &ret = dp[bits][v]; if (ret >= 0) { return ret; } assert ((bits & (1 << v)) == 1 << v); if (bits == 1 << v) { double c = 100 * (abs(x[0] - x[v]) + abs(y[0] - y[v])); return ret = c; } double mi = inf; double tot_w = 0; REP (i, 1, n + 1) { if (i != v && (bits & (1 << i))) { tot_w += w[i]; } } REP(i, 1, n + 1) { if ((bits & (1 << i)) == 0 || v == i) { continue; } double c = (tot_w + 100) * (abs(x[v] - x[i]) + abs(y[v] - y[i])); mi = min(mi, c + rec(bits ^ (1 << v), i)); } return ret = mi; } int main(void){ cin >> x[0] >> y[0]; cin >> n; double tot_w = 0; REP(i, 1, n+1) { cin >> x[i] >> y[i] >> w[i]; tot_w += w[i]; } double mi = inf; REP (i, 0, 2 << N) { fill_n(dp[i], N + 1, -1); } REP(i, 1, n + 1) { double c = (tot_w + 100) * (abs(x[0] - x[i]) + abs(y[0] - y[i])); mi = min(mi, c + rec((2 << n) - 2, i)); } printf("%.9f\n", (double)mi / 120.0 + tot_w); }