結果

問題 No.134 走れ！サブロー君
コンテスト
ユーザー rpy3cpp
提出日時 2015-07-08 01:07:25
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,719 bytes
コンパイル時間 78 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 16,384 KB
最終ジャッジ日時 2024-07-08 01:36:41
合計ジャッジ時間 8,519 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

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