結果
問題 | No.845 最長の切符 |
ユーザー |
|
提出日時 | 2022-07-16 18:31:31 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,081 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 90,144 KB |
最終ジャッジ日時 | 2024-06-28 18:28:02 |
合計ジャッジ時間 | 5,275 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 WA * 19 |
ソースコード
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 = [[0]*V for i in range(2**V)] # dpの長さは2^V必要for 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)