結果
問題 | No.134 走れ!サブロー君 |
ユーザー | rpy3cpp |
提出日時 | 2015-07-08 01:39:59 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 329 ms / 5,000 ms |
コード長 | 1,937 bytes |
コンパイル時間 | 106 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 17,208 KB |
最終ジャッジ日時 | 2024-10-14 17:14:44 |
合計ジャッジ時間 | 1,982 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 32 ms
11,008 KB |
testcase_01 | AC | 31 ms
10,880 KB |
testcase_02 | AC | 30 ms
10,880 KB |
testcase_03 | AC | 37 ms
10,880 KB |
testcase_04 | AC | 40 ms
11,008 KB |
testcase_05 | AC | 53 ms
11,520 KB |
testcase_06 | AC | 80 ms
12,288 KB |
testcase_07 | AC | 150 ms
13,976 KB |
testcase_08 | AC | 329 ms
17,208 KB |
testcase_09 | AC | 318 ms
17,204 KB |
testcase_10 | AC | 30 ms
11,008 KB |
testcase_11 | AC | 31 ms
11,008 KB |
testcase_12 | AC | 31 ms
11,008 KB |
testcase_13 | AC | 31 ms
11,008 KB |
testcase_14 | AC | 30 ms
11,008 KB |
ソースコード
import collections def read_data(): x0, y0 = map(int, input().split()) N = int(input()) XY = [(0, 0)] W = [0.0] for i in range(N): x, y, w = input().split() XY.append((int(x) - x0, int(y) - y0)) W.append(float(w)) return N, XY, W def solve(N, XY, W): global record T, N, XY, W = simplify(N, XY, W) dist = [[abs(xi - xj) + abs(yi - yj) for (xj, yj) in XY] for (xi, yi) in XY] time = T + wfs(N, W, dist) / 120.0 return time def simplify(N, XY, W): pos_w = collections.defaultdict(int) for (x, y), w in zip(XY, W): pos_w[x, y] += w newXY = [(0, 0)] newW = [0] del pos_w[0, 0] for (x, y), w in pos_w.items(): newXY.append((x, y)) newW.append(w) return sum(W), len(newW), newXY, newW def wfs(N, W, dist): frontiers = {(0, 1): (0, sum(W) + 100)} for n_used in range(1, N): new_frontiers = dict() for (pos, used_bits), (cum_t, cum_w) in frontiers.items(): dpos = dist[pos] for new_pos in range(N): if (1 << new_pos) & used_bits: continue new_cum_t = cum_t + cum_w * dpos[new_pos] new_cum_w = cum_w - W[new_pos] new_used_bits = used_bits | (1 << new_pos) if (new_pos, new_used_bits) in new_frontiers: ct, cw = new_frontiers[new_pos, new_used_bits] if ct > new_cum_t: new_frontiers[new_pos, new_used_bits] = (new_cum_t, new_cum_w) else: new_frontiers[new_pos, new_used_bits] = (new_cum_t, new_cum_w) frontiers = new_frontiers best_t = float('inf') for (pos, used_bits), (cum_t, cum_w) in frontiers.items(): t = cum_t + cum_w * dist[pos][0] if t < best_t: best_t = t return best_t N, XY, W = read_data() print(solve(N, XY, W))