読者です 読者をやめる 読者になる 読者になる

AOJ2254 模擬国内2011C Fastest Route

解法
bitDPで解く。
dp[S] := 状態Sでステージを全てクリアするのにかかる最小時間
dp[0] = 0

for S[0, 1<<N) for i[0, N)
  if Sのi番目のビットが立っていない
    dp[S | (1<<i)] = min(dp[S | (1<<i)], dp[i] + T[i][0] /*素手*/);
    for j[0,N)
      if Sのj番目のビットが立っている
        dp[ S | (1<<i)] = min(dp[S | (1<<i)], dp[S] + T[i][j+1])