結果
問題 | 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 sys readline = sys.stdin.readline X,Y = map(int,readline().split()) N = int(readline()) cities = [None] * N W = [-1] * N all_w = 0 for 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] * N for i in range(N): dist_from_start[i] = abs(cities[i][0] - X) + abs(cities[i][1] - Y) start_T = (all_w + 100) / 120 INF = 1 << 60 dp = [[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] = d dist[j][i] = d for status in range(1 << N): weight = 0 for i in range(N): if (status >> i) & 1 == 0: # まだ下ろしていない荷物 weight += W[i] speed = (weight + 100) / 120 for from_v in range(N): if (status >> from_v) & 1 == 0: continue for to_v in range(N): if (status >> to_v) & 1: continue next_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] = time ans = INF for i in range(N): arrival = dp[i][-1] + (100 / 120) * dist_from_start[i] if ans > arrival: ans = arrival print(ans)