題目鏈接： 點擊打開鏈接
題目： After coding so many days,Mr Acmer wants to have a good rest.So travelling is the best choice!He has decided to visit n cities(he insists on seeing all the cities!And he does not mind which city being his start station because superman can bring him to any city at first but only once.), and of course there are m roads here,following a fee as usual.But Mr Acmer gets bored so easily that he doesn't want to visit a city more than twice!And he is so mean that he wants to minimize the total fee!He is lazy you see.So he turns to you for help. 分析： 每天路徑最多訪問兩次，可以使用三進制狀態壓縮，d[S][j] 表示在狀態s下最后一個訪問j時的最小花費; 狀態轉移方程：d[S][k] = min(d[S][k], d[S-state[k]][j] + G[j][k]); ? ?不過這里通過狀態d[S][j] 轉移到 ---> d[S+state[k]][k] = min(d[S+state[k]][k], d[S][j]+G[j][k]);
代碼： #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector>using namespace std;const int maxn = 11; int n, m; int G[60000][maxn], state[11], vis[60000][maxn]; const int INF = 0x3f3f3f3f; int d[60000][maxn];void init(){state[0] = 1;for(int i = 1; i <= 10; ++i){state[i] = 3*state[i-1];}for(int i = 0; i < state[10]; ++i){int tmp = i;for(int j = 0; j < 10; ++j){vis[i][j] = tmp%3;tmp /= 3;}} } int deal(){memset(d, 0x3f, sizeof(d));for(int i = 0; i < n; ++i) d[state[i]][i] = 0;for(int i = 1; i < state[n]; ++i){for(int j = 0; j < n; ++j){if(d[i][j] == INF) continue;for(int k = 0; k < n; ++k){if(k==j) continue;if(vis[i][k] < 2 && G[j][k]!=INF){d[i+state[k]][k] = min(d[i+state[k]][k], d[i][j]+G[j][k]);}}}}int ans = INF;for(int i = 1; i < state[n]; ++i){int ok = 1;for(int j = 0; j < n; ++j){if(vis[i][j] == 0){ok = 0; break;}}if(ok){for(int j = 0; j < n; ++j){ans = min(ans, d[i][j]);}}}return ans; }int main() {init();while(~scanf("%d%d", &n, &m)){int u, v, w;memset(G, 0x3f, sizeof(G));for(int i = 0; i < m; ++i){scanf("%d%d%d", &u, &v, &w);u--, v--;if(w < G[u][v]){G[u][v] = G[v][u] = w;}}int ans = deal();if(ans == INF) ans = -1;printf("%d\n", ans);} }

總結

以上是生活随笔為你收集整理的hdu3001(状态压缩dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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