結果
問題 |
No.134 走れ!サブロー君
|
ユーザー |
|
提出日時 | 2021-08-28 17:17:18 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 2,379 ms / 5,000 ms |
コード長 | 679 bytes |
コンパイル時間 | 355 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 17,280 KB |
最終ジャッジ日時 | 2024-11-21 21:07:34 |
合計ジャッジ時間 | 8,287 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 |
ソースコード
nimotsu=[] x,y=map(int,input().split()) n=int(input()) nimotsu.append((x,y,0)) for _ in range(n): nimotsu.append(tuple(map(float,input().split()))) n+=1 INF=10**18 dp=[[INF]*n for _ in range(1<<n)] dp[0][0]=0 def t(weight): return (weight+100)/120 for s in range(1<<n): w=0 # 今持っている荷物の重さ for j in range(n): if not (s>>j)&1: w+=nimotsu[j][2] for v in range(n): if (s>>v)&1: continue xv,yv,_ =nimotsu[v] for u in range(n): xu,yu,wu=nimotsu[u] dp[s|(1<<v)][v]=min(dp[s|(1<<v)][v],dp[s][u]+t(w)*(abs(xu-xv)+abs(yu-yv))+wu ) ans=dp[(1<<n)-1][0] print(ans)