首页 > 代码库 > hdu 4568(状态压缩dp)
hdu 4568(状态压缩dp)
题意:一张n*m的网格内每个点有话费,还有若干个宝藏,问一个人要走进去拿走所有宝藏在走出来的最小花费。
思路:看宝藏只有13个直接想到了状压dp[i][j]拿了哪几个前一个为j的最小花费,先bfs+优先队列预处理出最短路,然后记忆化搜索就可。
代码如下:
1 /************************************************** 2 * Author : xiaohao Z 3 * Blog : http://www.cnblogs.com/shu-xiaohao/ 4 * Last modified : 2014-05-15 16:59 5 * Filename : C.cpp 6 * Description : 7 * ************************************************/ 8 9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <cmath> 14 #include <algorithm> 15 #include <queue> 16 #include <stack> 17 #include <vector> 18 #include <set> 19 #include <map> 20 #define MP(a, b) make_pair(a, b) 21 #define PB(a) push_back(a) 22 23 using namespace std; 24 typedef long long ll; 25 typedef pair<int, int> pii; 26 typedef pair<unsigned int,unsigned int> puu; 27 typedef pair<int, double> pid; 28 typedef pair<ll, int> pli; 29 typedef pair<int, ll> pil; 30 31 const int INF = 0x3f3f3f3f; 32 const double eps = 1E-6; 33 const int LEN = 210; 34 int Map[LEN][LEN], mp[LEN][LEN], out[LEN], in[LEN], dp[1<<13][20]; 35 int n, m, vn, N; 36 int xx[] = {0, 0, 1,-1}; 37 int yy[] = {1,-1, 0, 0}; 38 pii vex[LEN]; 39 40 bool J(int x, int y){ 41 if(x == 1 || x == n || y == 1 || y == m) return true; 42 return false; 43 } 44 45 bool Ja(int x, int y){ 46 if(x>0 && x<=n && y>0 && y<=m) return true; 47 return false; 48 } 49 50 struct P{ 51 int x, y, val; 52 bool operator<(const P a) const 53 { 54 return this->val > a.val; 55 } 56 }; 57 58 P mmp(int a, int b, int c){ 59 P ret; 60 ret.x = a;ret.y = b;ret.val = c; 61 return ret; 62 } 63 64 int Bfs(int sx, int sy, int ex, int ey){ 65 int vis[210][210] = {0}; 66 priority_queue<P> q; 67 q.push(mmp(sx, sy, 0)); 68 vis[sx][sy] = 1; 69 while(!q.empty()){ 70 P nv = q.top();q.pop(); 71 int x = nv.x, y = nv.y, val = nv.val; 72 if(ex < 0 && ey < 0){ 73 if(J(x, y)) return val; 74 } 75 else if(x == ex && y == ey) return val; 76 for(int i=0; i<4; i++){ 77 int tx = x + xx[i]; 78 int ty = y + yy[i]; 79 if(Ja(tx, ty) && !vis[tx][ty]){ 80 vis[tx][ty] = 1; 81 q.push(mmp(tx, ty, val + mp[tx][ty])); 82 } 83 } 84 } 85 return -1; 86 } 87 88 void init(){ 89 for(int i=0; i<vn; i++){ 90 for(int j=0; j<vn; j++){ 91 Map[i][j] = Bfs(vex[i].first, vex[i].second, vex[j].first, vex[j].second); 92 } 93 } 94 for(int i=0; i<vn; i++){ 95 int x = vex[i].first, y = vex[i].second; 96 out[i] = Bfs(x, y, -1, -1); 97 in[i] = out[i] + mp[x][y]; 98 } 99 } 100 101 int dfs(int x, int lv){ 102 if(dp[x][lv] != INF) return dp[x][lv]; 103 int cnt = 0; 104 for(int i=0; i<vn; i++){ 105 if(x & (1 << i)) cnt ++ ; 106 } 107 if(cnt == 1) return dp[x][lv] = in[lv]; 108 int ret = INF; 109 for(int i=0; i<vn; i++){ 110 if((x & (1<<i)) && i != lv){ 111 int &val = Map[i][lv]; 112 ret = min(ret, dfs(x^(1<<lv), i) + val); 113 } 114 } 115 return dp[x][lv] = ret; 116 } 117 118 int main() 119 { 120 // freopen("in.txt", "r", stdin); 121 122 int T, a, b; 123 scanf("%d", &T); 124 while(T--){ 125 scanf("%d%d", &n, &m); 126 memset(Map, 0x3f, sizeof Map); 127 memset(mp, 0, sizeof mp); 128 memset(dp, 0x3f, sizeof dp); 129 for(int i=1; i<=n; i++){ 130 for(int j=1; j<=m; j++){ 131 scanf("%d", &mp[i][j]); 132 if(mp[i][j] == -1) mp[i][j] = INF; 133 } 134 } 135 scanf("%d", &vn); 136 for(int i=0; i<vn; i++){ 137 scanf("%d%d", &a, &b); 138 a++, b++; 139 vex[i] = MP(a, b); 140 } 141 init(); 142 int ans = INF; 143 for(int i=0; i<vn; i++){ 144 ans = min(ans, dfs((1<<vn)-1, i) + out[i]); 145 } 146 if(ans != INF) printf("%d\n", ans); 147 else printf("0\n"); 148 } 149 return 0; 150 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。