結果

問題 No.134 走れ!サブロー君
ユーザー Ueki
提出日時 2019-05-16 12:49:59
言語 Python3
(3.7.1 + numpy 1.14.5 + scipy 1.1.0)
結果
WA   .
実行時間 -
コード長 1,723 Byte
コンパイル時間 48 ms
使用メモリ 8,200 KB
最終ジャッジ日時 2019-08-12 17:48:57

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
01.txt WA -
02.txt WA -
03.txt WA -
04.txt WA -
05.txt WA -
06.txt WA -
07.txt WA -
08.txt WA -
09.txt WA -
10.txt WA -
system_test1.txt WA -
system_test2.txt WA -
system_test3.txt WA -
system_test4.txt WA -
system_test5.txt WA -
テストケース一括ダウンロード

ソースコード

diff #
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def manhattan(item1, item2):
    return abs(item1[0]-item2[0])+abs(item1[1]-item2[1])


def calcCost(dropItem, last_visit, loading_weight):
    dist = manhattan(dropItem, last_visit)
    return (loading_weight+100)/120*dist+dropItem[2]


def calcLoadingWeight(current_state):
    """
    現在積んでいる重み
    """
    load = 0
    for i in range(N):
        if current_state >> i ^ 0:  # 積んでいる(0)なら加える
            load += items[i][2]
    return load


SX, SY = map(int, input().split())
N = int(input())
items = [list(map(float, input().split())) for _ in range(N)]

# dp[状態bit][最後に訪れた場所]
dp = [[float('inf')]*N for _ in range(1 << N)]

for i in range(1):
    dp[0][i] = 0

for mask in range(1 << N):
    for new_item in range(N):  # 次に行く場所
        if mask >> new_item & 1:
            continue

        new_state = mask | 1 << new_item  # 訪問後のbit
        loading_weight = calcLoadingWeight(mask)
        if mask == 0:  # 一番初めの訪問
            cost = calcCost(items[new_item], [SX, SY], loading_weight)
            dp[new_state][new_item] = cost
        else:
            for last_visit in range(N):
                if mask >> last_visit & 1:
                    cost = calcCost(items[new_item],
                                    items[last_visit], loading_weight)
                    dp[new_state][new_item] = min(
                        dp[new_state][new_item], dp[mask][last_visit]+cost)

ans = float('inf')
for i in range(N):
    # 最後に、始点に戻ってくるコストを加える
    ans = min(ans, dp[-1][i]+calcCost(items[i], [SX, SY], 0))
print(ans)
0