結果
問題 | No.845 最長の切符 |
ユーザー |
![]() |
提出日時 | 2023-10-25 17:35:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,361 ms / 3,000 ms |
コード長 | 617 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 82,492 KB |
実行使用メモリ | 89,892 KB |
最終ジャッジ日時 | 2024-09-25 05:54:18 |
合計ジャッジ時間 | 6,821 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
N,M = map(int,input().split())G = [[] for i in range(N)]for _ in range(M):a,b,c = map(int,input().split())G[a - 1].append([b - 1, c])G[b - 1].append([a - 1, c])dp = [[-1] * N for i in range(1 << N)]for i in range(N):dp[1 << i][i] = 0for i in range(1 << N):for v in range(N):if (i >> v) & 1 == 0:continuefor u, c in G[v]:if (i >> u) & 1:continuedp[i | (1 << u)][u] = max(dp[i | (1 << u)][u], dp[i][v] + c)ans = 0for i in range(1 << N):ans = max(ans, max(dp[i]))print(ans)