結果
問題 |
No.90 品物の並び替え
|
ユーザー |
|
提出日時 | 2021-04-30 15:04:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 64 ms / 5,000 ms |
コード長 | 758 bytes |
コンパイル時間 | 133 ms |
コンパイル使用メモリ | 82,464 KB |
実行使用メモリ | 65,536 KB |
最終ジャッジ日時 | 2024-07-18 12:13:23 |
合計ジャッジ時間 | 1,159 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 9 |
ソースコード
import sys def resolve(): inp = int2d() n,m = inp[0] graph = [[0]*n for _ in range(n)] for item1,item2,score in inp[1:]: graph[item1][item2] = score #bit, last vertex dp = [[0]*n for _ in range(1<<n)] for bit in range(1<<n): for vertex in range(n): if not(bit & 1<<vertex): continue if bit == 1<<vertex: break prebit = bit ^ 1<<vertex delta = 0 for shift in range(n): if prebit & 1<<shift: delta += graph[shift][vertex] dp[bit][vertex] = max(dp[prebit]) + delta print(max(dp[-1])) def str1d():return sys.stdin.read().splitlines() def int2d():return [list(map(int,s.split())) for s in str1d()] resolve()