結果

問題 No.134 走れ！サブロー君
ユーザー rpy3cpprpy3cpp
提出日時 2015-07-08 01:07:25
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
TLE  
実行時間 -
コード長 1,719 bytes
コンパイル時間 177 ms
コンパイル使用メモリ 10,972 KB
実行使用メモリ 13,188 KB
最終ジャッジ日時 2023-09-22 09:28:09
合計ジャッジ時間 8,856 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
8,812 KB
testcase_01 AC 18 ms
8,704 KB
testcase_02 AC 18 ms
8,736 KB
testcase_03 AC 61 ms
8,700 KB
testcase_04 AC 358 ms
8,756 KB
testcase_05 AC 1,239 ms
8,744 KB
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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]
    used = [False] * N
    used[0] = True
    n_used = 1
    pos = 0
    cum_d = 0
    cum_t = 0
    record = float('inf')
    time = T + dfs(N, W, dist, cum_d, cum_t, pos, used, n_used) / 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 dfs(N, W, dist, cum_d, cum_t, pos, used, n_used):
    global record
    if n_used == N:
        cum_t += (cum_d + dist[pos][0]) * 100
        if cum_t < record:
            record = cum_t
        return record
    best_time = float('inf')
    dpos = dist[pos]
    for new_pos, is_used in enumerate(used):
        if is_used:
            continue
        new_cum_d = cum_d + dpos[new_pos]
        new_cum_t = cum_t + new_cum_d * W[new_pos]
        if new_cum_t >= record:
            continue
        used[new_pos] = True
        time = dfs(N, W, dist, new_cum_d, new_cum_t, new_pos, used, n_used + 1)
        if best_time > time:
            best_time = time
        used[new_pos] = False
    return best_time

N, XY, W = read_data()
print(solve(N, XY, W))
0