結果
問題 | No.845 最長の切符 |
ユーザー |
|
提出日時 | 2022-07-16 18:34:57 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,133 bytes |
コンパイル時間 | 136 ms |
コンパイル使用メモリ | 82,764 KB |
実行使用メモリ | 95,656 KB |
最終ジャッジ日時 | 2024-06-28 18:32:16 |
合計ジャッジ時間 | 5,508 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 2 WA * 25 |
ソースコード
n,m = map(int,input().split())V = nE = mG = [[-float('inf')]*V for i in range(V)] # 存在しないパスはinfになるように、最初にすべてinfにしておくfor i in range(E):s,t,d = map(int,input().split())s -= 1t -= 1G[s][t] = d # s,tは0以上V-1以下なので、デクリメントの必要はないG[t][s] = d # s,tは0以上V-1以下なので、デクリメントの必要はないdp = [[-float('inf')]*V for i in range(2**V)] # dpの長さは2^V必要for i in range(V):dp[2**i][0] = 0for S in range(2**V): # Sは集合をbitで表しているfor v in range(V): # vは配られる側の要素を表しているfor u in range(V): # uは配る側の要素を表しているif u == v:continueif not (S >> u) & 1:# and S != 0: # ①continueif (S >> v) & 1 == 0: # ②if dp[S][u] + G[u][v] > dp[S | (1 << v)][v]:dp[S | (1 << v)][v] = dp[S][u] + G[u][v] # ③ans = 0for i in range(2**V):for j in range(V):ans = max(ans,dp[i][j])print(ans)