POJ 3311 Hie with the Pie

問題

n+1頂点からなるグラフが、距離行列の形で与えられる。
0番の頂点を出発し、全ての頂点を一度以上通り、0番の頂点へ戻ってくるのに必要な移動距離の最小値を求めよ。

制約条件

n≦10

方針

ビットDPをベルマンフォードっぽくやる。
一つのbitにつき、高々n回更新すればいい。

ソースコード

int n,d[11][11];
int dp[11][1<<11];

int main(){
  while(scanf("%d",&n),n){
    n++;
    rep(i,n)rep(j,n)scanf("%d",d[i]+j);
    rep(i,n)rep(j,1<<n)dp[i][j]=(int)1e9;
    dp[0][0]=0;
    rep(j,1<<n)rep(it,n)rep(i,n)rep(k,n)
    dp[k][j|1<<k]=min(dp[k][j|1<<k],dp[i][j]+d[i][k]);
    printf("%d\n",dp[0][(1<<n)-1]);
  }
  return 0;
}