題目鏈接：點擊進入

題目

題意

從 0 出發經過所有點最后再回到 0 點的最短距離（ 可以多次經過同一個點 ）

思路

dp [ i ] [ j ] 代表經過狀態 i 里的點最后到 j 點經過的距離
首先用 floyd 求每兩個點間的最短距離,然后從 0 -（ 1<<n ） 枚舉每個狀態，更新dp值
如果這個狀態只經過 j 這個點，那么 dp [ i ] [ j ] = dis [ 0 ] [ j ];（一開始就是從 0 出發）
如果經過了多個點，可以通過枚舉中間點，來更新 dp 值（ 類似 floyd ）

代碼

// #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") //#pragma GCC optimize(3)//O3 //#pragma GCC optimize(2)//O2 //#include<bits/stdc++.h> #include<iostream> #include<string> #include<map> #include<set> //#include<unordered_map> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #include<iomanip> #include<cmath> #include<bitset> #include<fstream> #define X first #define Y second #define best 131 #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define lowbit(x) x & -x #define inf 0x3f3f3f3f #define max(a,b) a>b?a:b #define min(a,b) a<b?a:b //#define int long long //#define double long double //#ifndef ONLINE_JUDGE freopen("data.in.txt","r",stdin); //freopen("data.out.txt","w",stdout); #endif //???t?áè? using namespace std; typedef long long ll; typedef unsigned long long ull; const double pai=acos(-1.0); const int Mod=998244353; const double eps=1e-9; const int N=26; const int mod=1e8; const int maxn=1e6+10;/*--------------------------------------------*/ inline int read() {int data=0,w=1; char ch=0;while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();if(ch=='-') w=-1,ch=getchar();while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data*w; } /*--------------------------------------------*/int n,m,dis[12][12]; int dp[1<<12][12]; int main() { // ios::sync_with_stdio(false); // cin.tie(0);cout.tie(0);while(cin>>n){if(n==0) break;for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)cin>>dis[i][j];for(int k=0;k<=n;k++)for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)if(dis[i][j]>dis[i][k]+dis[k][j])dis[i][j]=dis[i][k]+dis[k][j];for(int i=0;i<(1<<n);i++)for(int j=1;j<=n;j++)dp[i][j]=inf;for(int i=0;i<(1<<n);i++){for(int j=1;j<=n;j++){if(i&(1<<(j-1)))//如果經過這個城市{if(i==(1<<(j-1))) dp[i][j]=dis[0][j];else{for(int k=1;k<=n;k++)if(i&(1<<(k-1))&&j!=k)dp[i][j]=min(dp[i][j],dp[i^(1<<(j-1))][k]+dis[k][j]);}}}}int ans=inf;for(int i=1;i<=n;i++)ans=min(ans,dp[(1<<n)-1][i]+dis[i][0]);cout<<ans<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的POJ - 3311- Hie with the Pie （ 状压dp ）的全部內容，希望文章能夠幫你解決所遇到的問題。

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