結果
問題 |
No.134 走れ!サブロー君
|
ユーザー |
|
提出日時 | 2021-05-18 05:18:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 400 ms / 5,000 ms |
コード長 | 1,707 bytes |
コンパイル時間 | 356 ms |
コンパイル使用メモリ | 82,252 KB |
実行使用メモリ | 96,316 KB |
最終ジャッジ日時 | 2024-10-07 21:02:10 |
合計ジャッジ時間 | 4,129 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
#region Header #!/usr/bin/env python3 # from typing import * import sys import io import math import collections import decimal import itertools import bisect import heapq def input(): return sys.stdin.readline()[:-1] # sys.setrecursionlimit(1000000) #endregion # _INPUT = """0 0 # 3 # 100 178 100 # 23 25 40 # 34 31 90 # """ # sys.stdin = io.StringIO(_INPUT) def main(): x0, y0 = map(int, input().split()) Point = [] Point.append((x0, y0, 0.0)) N = int(input()) for _ in range(N): x, y, w = input().split() Point.append((int(x), int(y), float(w))) N += 1 total_weight = sum(Point[i][2] for i in range(N)) dp = [[10**10] * N for _ in range(1<<N)] dp[1][0] = 0 for s in range(1, 1<<N): weight = total_weight - sum(Point[i][2] for i in range(N) if s & (1<<i)) move_time = (weight+100)/120 for next_point in range(N): if s & (1<<next_point): continue for last_point in range(N): if s & (1<<last_point) == 0: continue dist = abs(Point[next_point][0] - Point[last_point][0]) + abs(Point[next_point][1] - Point[last_point][1]) t1 = dp[s][last_point] + dist * move_time + Point[next_point][2] s1 = s | (1<<next_point) dp[s1][next_point] = min(dp[s1][next_point], t1) min_time = 10**10 for last_point in range(1, N): dist = abs(Point[last_point][0] - Point[0][0]) + abs(Point[last_point][1] - Point[0][1]) time = dp[(1<<N)-1][last_point] + dist * (100/120) min_time = min(min_time, time) print(min_time) if __name__ == '__main__': main()