AOJ : 2254 - 最短ルート (Fastest Route)

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2254
日本語の問題文なので省略です.

アルゴリズム

すでにどこのステージに訪れたかを16ビットで管理して, あとはbitDP.

• dp[bit] = すでに訪れたステージがbitのときの, 攻略最小時間

プログラム

int n;
int t[20][20];
int dp[100000];

void solve(){
  int to = (1<<n);
  rep(i,to+2) dp[i] = INT_MAX;
  dp[0] = 0;

  rep(i,to){
    if(dp[i] == INT_MAX) continue;
    rep(next,n){
      if((i & (1<<next)) != 0) continue;
      int minCost = t[next][0];
      rep(j,n){
        if((i & (1<<j)) != 0){
          minCost = min(minCost,t[next][j+1]);
        }
      }

      int bit = (i | (1<<next));
      dp[bit] = min(dp[bit],dp[i]+minCost);
    }
  }

  cout<<dp[to-1]<<endl;
}

int main(){
  while(cin>>n,n){
    rep(i,n){
      rep(j,n+1){
        cin>>t[i][j];
      }
    }
    solve();
  }
}