地址：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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。