結果
問題 | No.357 品物の並び替え (Middle) |
ユーザー |
|
提出日時 | 2022-10-25 14:16:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 80 ms / 5,000 ms |
コード長 | 926 bytes |
コンパイル時間 | 144 ms |
コンパイル使用メモリ | 82,468 KB |
実行使用メモリ | 69,616 KB |
最終ジャッジ日時 | 2024-07-03 13:22:39 |
合計ジャッジ時間 | 1,878 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#!/usr/bin/python# -*- coding: utf-8 -*-# importfrom sys import stdin, setrecursionlimitsetrecursionlimit(10**8)def int_map():return map(int,input().split())def int_list():return list(map(int,input().split()))def int_mtx(N):x = [list(map(int, stdin.readline().split())) for _ in range(N)]return xdef str_mtx(N):x = [list(stdin.readline()[:-1]) for _ in range(N)]return xdef print_space(l):return print(" ".join([str(x) for x in l]))""" main code """N,M = int_map()G = [[] for _ in range(N)]for _ in range(M):i,j,c = int_map()G[j].append([i,c])dp = [0 for _ in range(2**N)]for s in range(2**N):for j in range(N):if s >> j & 1 == 0:cst = 0for i,c in G[j]:if s >> i & 1 == 1:cst += cdp[s+2**j] = max(dp[s+2**j], dp[s]+cst)print(dp[2**N-1])