結果
問題 | No.845 最長の切符 |
ユーザー |
|
提出日時 | 2022-07-16 18:51:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 624 ms / 3,000 ms |
コード長 | 1,159 bytes |
コンパイル時間 | 150 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 100,992 KB |
最終ジャッジ日時 | 2024-06-28 18:49:57 |
合計ジャッジ時間 | 6,134 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
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] = max(d,G[s][t]) # s,tは0以上V-1以下なので、デクリメントの必要はないG[t][s] = max(d,G[s][t]) # 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][i] = 0for S in range(2**V): # Sは集合をbitで表しているfor v in range(V): # vは配られる側の要素を表しているfor u in range(V): # uは配る側の要素を表しているif not (S >> u) & 1: # ①continueif (S >> v) & 1 == 0: # ②if dp[S][u] + G[u][v] > dp[S | (1 << v)][v]:#print(dp[S][u],u,v)dp[S | (1 << v)][v] = dp[S][u] + G[u][v] # ③#print(dp)#print(G)ans = 0for i in range(2**V):for j in range(V):ans = max(ans,dp[i][j])print(ans)