AOJ 2254 - Fastest Route

やるだけ．

解法

bitDP．

コード

たまにはループで．

#include <cstdio>
#include <algorithm>

int T[16][17], T_[1<<16][16];
int dp[1<<16][16];

int main(){
    int N;
    while(scanf("%d", &N), N){
        for(int i=0;i<N;i++){
            for(int j=0;j<=N;j++){
                scanf("%d", &T[i][j]);
            }
        }

        for(int i=0;i<1<<N;i++){
            for(int j=0;j<N;j++){
                int mn = T[j][0];
                for(int k=0;k<N;k++){
                    if(!(i >> k & 1)){continue;}
                    mn = std::min(mn, T[j][k+1]);
                }
                T_[i][j] = mn;
            }
        }

        for(int i=0;i<1<<N;i++){
            for(int j=0;j<N;j++){
                dp[i][j] = i == 0 ? 0 : 1001001001;
            }
        }

        for(int i=0;i<1<<N;i++){
            for(int j=0;j<N;j++){
                for(int k=0;k<N;k++){
                    if(i >> k & 1){continue;}
                    int ni = i | (1 << k);
                    dp[ni][k] = std::min(dp[ni][k], dp[i][j] + T_[i][k]);
                }
            }
        }

        int res = 1001001001;
        for(int i=0;i<N;i++){
            res = std::min(res, dp[(1<<N)-1][i]);
        }

        printf("%d\n", res);
    }
}