結果
問題 | No.134 走れ!サブロー君 |
ユーザー |
|
提出日時 | 2022-10-25 00:47:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 91 ms / 5,000 ms |
コード長 | 1,396 bytes |
コンパイル時間 | 398 ms |
コンパイル使用メモリ | 82,148 KB |
実行使用メモリ | 77,452 KB |
最終ジャッジ日時 | 2024-07-03 03:12:02 |
合計ジャッジ時間 | 1,787 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
import sysreadline = sys.stdin.readlineX,Y = map(int,readline().split())N = int(readline())cities = [None] * NW = [-1] * Nall_w = 0for i in range(N):x,y,w = readline().split()cities[i] = [int(x),int(y)]W[i] = float(w)all_w += W[i]dist_from_start = [0] * Nfor i in range(N):dist_from_start[i] = abs(cities[i][0] - X) + abs(cities[i][1] - Y)start_T = (all_w + 100) / 120INF = 1 << 60dp = [[INF] * (1 << N) for i in range(N)]for i in range(N):dp[i][1 << i] = start_T * dist_from_start[i] + W[i]dist = [[0] * N for i in range(N)]for i in range(N - 1):for j in range(i + 1, N):d = abs(cities[i][0] - cities[j][0]) + abs(cities[i][1] - cities[j][1])dist[i][j] = ddist[j][i] = dfor status in range(1 << N):weight = 0for i in range(N):if (status >> i) & 1 == 0: # まだ下ろしていない荷物weight += W[i]speed = (weight + 100) / 120for from_v in range(N):if (status >> from_v) & 1 == 0:continuefor to_v in range(N):if (status >> to_v) & 1:continuenext_status = status | (1 << to_v)time = dp[from_v][status] + speed * dist[from_v][to_v] + W[to_v]if dp[to_v][next_status] > time:dp[to_v][next_status] = timeans = INFfor i in range(N):arrival = dp[i][-1] + (100 / 120) * dist_from_start[i]if ans > arrival:ans = arrivalprint(ans)