题目描述
披萨店给n个地方送披萨，已知各地方（包括披萨店）之间花费的时间，求送完所有地方并回到店花费的最小时间。
输入
第一行：n， n≤10
接下来一个（n+1）*（n+1）的矩阵，0到n每个点之间的距离。
输出
最小时间。
样例输入
3 0 1 10 10 1 0 1 2 10 1 0 10 10 2 10 0 0
样例输出
8
题解
状压dp。
floyd求出每个点间的最短路，dp[ s ][ i ] 表示当前状态为 s ，在第 i 号点花费的最小时间。转移具体看程序。
#include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define ll long long const int maxn=10+5; const int maxm=(1<<10)+50; const int inf=2e9+4e8; int n,dis[maxn][maxn],state[maxm]; int dp[maxm][maxn]; template<typename T>void read(T& aa){ char cc; ll ff;aa=0;cc=getchar();ff=1; while((cc<'0'||cc>'9')&&cc!='-') cc=getchar(); if(cc=='-') ff=-1,cc=getchar(); while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar(); aa*=ff; } int main(){ while(scanf("%d",&n)==1&&n){ int ans=inf; memset(dp,0,sizeof(dp)); for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) read(dis[i][j]); for(int k=0;k<=n;k++) for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); for(int state=0;state<(1<<n);state++) for(int i=1;i<=n;i++){ if(state&(1<<i-1)){ if(state==(1<<i-1)) dp[state][i]=dis[0][i]; else{ dp[state][i]=inf; for(int j=1;j<=n;j++){ if(j==i) continue; if(!(state&(1<<j-1))) continue; dp[state][i]=min(dp[state][i],dp[state^(1<<i-1)][j]+dis[j][i]); } } } } for(int i=1;i<=n;i++) ans=min(ans,dp[(1<<n)-1][i]+dis[i][0]); printf("%d ",ans); } return 0; }