【题目分析】 状压DP
【代码】
#include <cstdio> #include <cmath> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int dp[4000][15]; int map[15][15],n; int main() { while (scanf("%d",&n)!=EOF&&n) { n++; for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) scanf("%d",&map[i][j]); for (int k=1;k<=n;++k) for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) map[i][j]=min(map[i][j],map[i][k]+map[k][j]); memset(dp,0x3f,sizeof dp); dp[0][1]=0; for (int i=1;i<=n;++i) for (int j=0;j<(1<<n);++j) for (int now=1;now<=n;++now) for (int k=1;k<=n;++k) if (!(j&(1<<(k-1)))) dp[j|(1<<(k-1))][k]=min(dp[j|(1<<(k-1))][k],dp[j][now]+map[now][k]); printf("%d\n",dp[(1<<n)-1][1]); } }