题意：tsp问题，经过图中所有的点并回到原点的最短距离。
解题关键：floyd+状态压缩dp，注意floyd时k必须在最外层
转移方程：$dp[S][i] = min (dp[S wedge (1 < < (i - 1))][k] + dis[k][j],dp[S][i])$
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #define inf 100000000 using namespace std; int dis[12][12]; int dp[1<<11][12]; int n,ans; int main(){ while(scanf("%d",&n)&&n){ 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++) dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]); for(int S=0;S<=(1<<n)-1;S++) for(int i=1;i<=n;i++){ if(S&(1<<(i-1)))//状态S中已经过城市i { if(S==(1<<(i-1))) dp[S][i]=dis[0][i]; else{ dp[S][i]=inf; for(int j=1;j<=n;j++){ if(S&(1<<(j-1))&&i!=j)//枚举不是城市I的其他城市 dp[S][i]=min(dp[S^(1<<(i-1))][j]+dis[j][i],dp[S][i]); } } } } int ans=inf; for(int i=1;i<=n;i++){ ans=min(ans,dp[(1<<n)-1][i]+dis[i][0]); } printf("%d ",ans); } return 0; }
改进了一下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cstdlib> #include<cmath> #define inf 100000000 using namespace std; int dis[12][12]; int dp[1<<11][12]; int n,ans; int main(){ while(scanf("%d",&n)&&n){ 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++) dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]); for(int S=0;S<=(1<<(n+1))-1;S++) for(int i=0;i<=n;i++) if(S&(1<<i))//状态S中已经过城市i { if(S==(1<<i)) dp[S][i]=dis[0][i]; else{ dp[S][i]=inf; for(int j=0;j<=n;j++){ if(S&(1<<j)&&i!=j)//枚举不是城市I的其他城市 dp[S][i]=min(dp[S^(1<<i)][j]+dis[j][i],dp[S][i]); } } } printf("%d ",dp[(1<<(n+1))-1][0]); } return 0; }