結果

問題 No.845 最長の切符
ユーザー vwxyzvwxyz
提出日時 2024-04-07 20:28:52
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 597 bytes
コンパイル時間 109 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 35,104 KB
最終ジャッジ日時 2024-10-01 04:42:33
合計ジャッジ時間 6,779 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 13 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

N,M=map(int,input().split())
graph=[[] for x in range(N)]
for m in range(M):
a,b,c=map(int,input().split())
a-=1;b-=1
graph[a].append((b,c))
graph[b].append((a,c))
inf=1<<30
dp=[[-inf]*N for bit in range(1<<N)]
for bit in range(1,1<<N):
for x in range(N):
if bit==1<<x:
dp[bit][x]=0
break
else:
for y in range(N):
if bit&1<<y:
for x,c in graph[y]:
if bit&1<<x:
dp[bit][y]=max(dp[bit][y],dp[bit^1<<y][x]+c)
ans=max(max(dp[bit]) for bit in range(1<<N))
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0