題目鏈接：點擊查看

題目大意：求從0開始的最短哈密頓路徑，并且要求了某些點的先后順序

題目分析：哈密頓路徑：由指定的起點前往指定的終點，途中經(jīng)過所有其他節(jié)點且只經(jīng)過一次（百度百科）

既然按照一定的次序求最短路，可以模仿floyd求最短路的思想，然后套用狀態(tài)壓縮的模板來做，在狀態(tài)壓縮的過程中，1表示該點已經(jīng)走過，0表示該點還未走過，dp[i][j]代表狀態(tài)i到終點j的最短距離，那么初始化就是dp[1][0]=0，其余都為inf

---

?2019.11.28更新：

看了大藍(lán)書后學(xué)了一種新的方法實現(xiàn)哈密頓路徑，比之前這個代碼更好理解更好實現(xiàn)了，特地來更新一下

?

直接上代碼吧，注釋比較清晰，有一點需要注意，可能是數(shù)據(jù)比較水的原因，用memset會MLE，但用for循環(huán)穩(wěn)過

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;const int inf=0x3f3f3f3f;const int N=(1<<21)+100;int dp[N][25];//dp[i][j]代表狀態(tài)i到終點j的最短距離，狀態(tài)：1表示已經(jīng)走過該點，0表示未走過 int f[25];int d[25][25];int main() { // freopen("input.txt","r",stdin);int n,m;while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<(1<<n);i++)for(int j=0;j<n;j++)dp[i][j]=inf;for(int i=0;i<n;i++)f[i]=0;dp[1][0]=0;//初始化 for(int i=0;i<n;i++){for(int j=0;j<n;j++){scanf("%d",&d[i][j]);}}while(m--){int u,v;scanf("%d%d",&u,&v);f[v]|=(1<<u);}for(int i=0;i<(1<<n);i++){for(int j=0;j<n;j++){if(dp[i][j]==inf)continue;for(int k=0;k<n;k++){if(d[j][k]==-1)continue;if(!(i&(1<<j)))//沒走過j點，故不能用j點當(dāng)中間點連接continue;if((i&(1<<k)))//已經(jīng)走過k點，根據(jù)哈密頓路徑的性質(zhì)不能重復(fù)經(jīng)過某個頂點continue;if((f[k]&i)!=f[k])//還未滿足先行條件continue;dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+d[j][k]);//狀態(tài)轉(zhuǎn)移方程}}}int ans=inf;for(int i=0;i<n;i++)ans=min(ans,dp[(1<<n)-1][i]);if(ans==inf)cout<<-1<<endl;elsecout<<ans<<endl;}return 0; }

更新：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=22;int maze[N][N],f[N];int d[1<<N][N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m;while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++)for(int j=0;j<n;j++){scanf("%d",&maze[i][j]);if(maze[i][j]==-1)maze[i][j]=inf;}for(int i=0;i<1<<n;i++)for(int j=0;j<n;j++)d[i][j]=inf;for(int i=0;i<n;i++)f[i]=0;d[1][0]=0;while(m--){int u,v;scanf("%d%d",&u,&v);f[v]|=(1<<u);}for(int i=1;i<1<<n;i++)//枚舉狀態(tài) {for(int j=0;j<n;j++)//枚舉終點 {if((f[j]&i)!=f[j])//若終點的前置點都沒有滿足，直接剪枝 continue;if(i>>j&1){for(int k=0;k<n;k++)//枚舉起點{d[i][j]=min(d[i][j],d[i^1<<j][k]+maze[k][j]);} }} }int ans=inf;for(int i=0;i<n;i++)ans=min(ans,d[(1<<n)-1][i]);if(ans==inf)printf("-1\n");elseprintf("%d\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 3538 A sample Hamilton path(最短哈密顿路径+状压dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。