poj 3311(状压DP+最短路)

poj 3311
经典TSP问题，之前做的时候被虐，现在来做就是一道水题。
设$dp(S, i)$为状态$i$最后访问到$j$城市的最优解，那么有状态转移方程
$$dp(S, i) = min(dp(S-i, j), dis(j, i))$$
其中$j$是已经访问过的城市(即在$S$中)，$dis$是两点最短路。
边界是$dp(S, i) = dis(0, i)$，当且仅当即只访问了点$i$
答案是$min(dp(E)(i) + dis(i, 0))$，其中$E$为$n$位$1$的二进制数(即全部访问)
注意图不是对称的，所以$dis(i, j)$是有序的，从$j$到$i$必须是$dis(j, i)$而不是$dis(i, j)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 10 + 5;
int n, dis[MAXN][MAXN], dp[1<<MAXN][MAXN]; //dp[st[i]][j] 设 状态i最后访问到j城市的最优解 
void clean() {
    ms(dis, 63), ms(dp, 63); 
}
void solve() {
    clean();
    for (int i=0;i<=n;i++) 
    for (int j=0;j<=n;j++) scanf("%d", &dis[i][j]);
    for (int k=0;k<=n;k++) 
    for (int i=0;i<=n;i++) 
    for (int j=0;j<=n;j++) if (k!=i&&k!=j&&i!=j) dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);//floyd
    for (int S=1;S<(1<<n);S++) {//枚举每个状态
        for (int i=1;i<=n;i++) {//枚举每个点 
            if (S&(1<<(i-1))) {//这个点在S中(已被访问) 
                if (S==(1<<(i-1))) {//如果S只访问了i 
                    dp[S][i] = dis[0][i];//DP边界
                } else {
                    for (int j=1;j<=n;j++) if (i!=j) {//找每个访问过的点j且这个点不是i
                        if (S&(1<<(j-1))) {
                            dp[S][i] = min(dp[S][i], dp[S^(1<<(i-1))][j] + dis[j][i]);
                            //图不对称所以必须是dis[j][i]而不是dis[i][j] 
                            //找中间点更新值，类似floyd 
                        }
                    }
                }
            }
        }
    }
    int ans = 1000000000;
    for (int i=1;i<=n;i++) ans = min(ans, dp[(1<<n)-1][i] + dis[i][0]);
    printf("%d\n", ans);
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d", &n)==1&&n) solve();
    return 0;
}