題意

n(n<=10)個城市，知道每個城市間的旅行費用，但每個城市最多走兩遍。問最小花費是多少 。

也就是每個城市可以走兩次的tsp問題。

---

分析

最多走兩次，三進制0 1 2可滿足，即用三進制狀壓。與二進制不同的地方就是先要預處理三進制，并且還要用flag記錄是否訪問了所有節點。詳見代碼。

---

代碼

#include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<vector> #include<cctype> #include<set> #include<map> #include<queue> #include<stack> #include<iomanip> #include<sstream> #include<limits> #define ll long long #define inf 0x3f3f3f3f using namespace std; const ll INF = 1e18; const int maxn = 2e5+10; const ll MOD = 1000000007; const double EPS = 1e-10; const double Pi = acos(-1.0); int G[110][110],dp[60000][12],tir[60000][12],s[12]; int main(){ #ifdef LOCALfreopen("C:\\Users\\lanjiaming\\Desktop\\acm\\in.txt","r",stdin);//freopen("output.txt","w",stdout); #endif //ios_base::sync_with_stdio(0);int n,m;s[0] = 1;for(int i = 1; i <= 10; i++) s[i] = s[i-1]*3;for(int i=0; i<=s[10]; i++) //三進制記錄 i狀態下節點j經過的次數{int t=i;for(int j = 0; j < 10; j++){tir[i][j]=t%3;t/=3;}}while(scanf("%d%d",&n,&m)!=EOF){memset(dp,inf,sizeof dp);memset(G,inf,sizeof G);for(int i = 0; i < n; i++) dp[s[i]][i] = 0; //可從任何一點開始出發for(int i = 0; i < m ;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);u--;v--;G[u][v] = G[v][u] = min(w,G[u][v]);}int ans = inf;for(int i = 0; i < s[n]; i++){bool flag = true; //判斷是否經過所有點for(int j = 0; j < n; j++){if (tir[i][j] == 0) flag = false;if (dp[i][j] == inf) continue;for(int k = 0; k < n; k++){if (j == k || tir[i][k] == 2) continue; //節點k走過兩次if (G[k][j] == inf) continue;dp[i+s[k]][k] = min(dp[i+s[k]][k],dp[i][j] + G[j][k]);}}if (flag)for(int k = 0; k < n; k++) ans = min(ans,dp[i][k]);}if (ans == inf) puts("-1");else printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的HDU 3001 Travelling (三进制状压dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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