题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1119

题解：状压dp存一下车有没有被搞过的状态就行。

#include <iostream>#include <cstring>#include <cstdio>using namespace std;typedef long long ll;ll dp[1 << 15] , val[15][15];int main() {    int t , Case = 0;    scanf("%d" , &t);    while(t--) {        int n;        scanf("%d" , &n);        for(int i = 0 ; i < n ; i++) {            for(int j = 0 ; j < n ; j++) {                scanf("%lld" , &val[i][j]);            }        }        for(int i = 0 ; i < (1 << n) ; i++) dp[i] = (ll)1234567 * (ll)1234567;        dp[0] = 0;        for(int i = 0 ; i < (1 << n) ; i++) {            for(int j = 0 ; j < n ; j++) {                if(i & (1 << j)) continue;                else {                    ll sum = val[j][j];                    for(int k = 0 ; k < n ; k++) {                        if(i & (1 << k)) {                            sum += val[j][k];                        }                    }                    dp[i | (1 << j)] = min(dp[i | (1 << j)] , dp[i] + sum);                }            }        }        printf("Case %d: %lld\n" , ++Case , dp[(1 << n) - 1]);    }    return 0;}

lightoj 1119 - Pimp My Ride（状压dp）