POJ-3311 Hie with the Pie

地址：http://poj.org/problem?id=3311

思路：状态压缩dp,dp[i][j]：表示在状态i以点j为结尾时的最小距离。状态i表示已经走过了点，对于n个点，一共有0 -> (1<<n)-1个状态，因此

dp[i][j]=min{dp[i-去除的点j][k]+G[k][j]}

dp[i+新加入的点j][j]=min{dp[i][k]+G[k][j]}

Code1 :

#include<iostream> #include<cstring> using namespace std;const int MAX_N=15; const int MAX_S=1050; int n; int G[MAX_N][MAX_N]; int dp[MAX_S][MAX_N];void Floyd(); int main() {ios::sync_with_stdio(false);while(cin>>n&&n){memset(dp,0,sizeof(dp));for(int i=0;i<=n;++i)for(int j=0;j<=n;++j)cin>>G[i][j];Floyd();for(int i=1;i<=n;++i) dp[1<<(i-1)][i]=G[0][i];int s=(1<<n)-1;for(int i=1;i<=s;++i)for(int j=1,p=i;p;p>>=1,++j)if(p&1){for(int k=1,pp=i;pp;pp>>=1,++k)if(pp&1&&j!=k){if(!dp[i][j]) dp[i][j]=dp[i-(1<<(j-1))][k]+G[k][j];else dp[i][j]=min(dp[i][j],dp[i-(1<<(j-1))][k]+G[k][j]);}}int ans=dp[s][1]+G[1][0];for(int i=2;i<=n;++i)ans=min(ans,dp[s][i]+G[i][0]);cout<<ans<<endl;}return 0; }void Floyd() {for(int k=0;k<=n;++k)for(int i=0;i<=n;++i)for(int j=0;j<=n;++j)G[i][j]=min(G[i][j],G[i][k]+G[k][j]); }

Code 2:

#include<iostream> #include<cstring> using namespace std;const int MAX_N=15; const int MAX_S=1<<MAX_N; int n; int G[MAX_N][MAX_N]; int dp[MAX_S][MAX_N];void Floyd(); int main() {ios::sync_with_stdio(false);while(cin>>n&&n){memset(dp,-1,sizeof(dp));for(int i=0;i<=n;++i)for(int j=0;j<=n;++j)cin>>G[i][j];Floyd();dp[1][0]=0;int s=(1<<(n+1))-1;for(int i=1;i<=s;++i)for(int j=0,p=i|1;p;p>>=1,++j)if((p&1)&&dp[i][j]!=-1){for(int k=0;k<=n;++k)if(dp[i|(1<<k)][k]==-1) dp[i|(1<<k)][k]=dp[i][j]+G[j][k];else dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+G[j][k]);}cout<<dp[s][0]<<endl;}return 0; }void Floyd() {for(int k=0;k<=n;++k)for(int i=0;i<=n;++i)for(int j=0;j<=n;++j)G[i][j]=min(G[i][j],G[i][k]+G[k][j]); }

 

总结

以上是生活随笔为你收集整理的POJ-3311 Hie with the Pie的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。