【题意】：地图中有K种物品, 没有收集资源时，每走一步用能量1，挖掘和收集资源 i 需要能量Ai ，收集了资源 i 后, 每走一步，消耗能量需要加Bi。问最后收集完K种物品并且回到起点的最小消耗。

【题解】：采用了优先队列+状态压缩bfs，这里要预处理好携带了状态s的代价cost[s]，之后的bfs该怎么做就怎么做。这里用优先队列有个好处，这样就保证每次出队的都是最优的点，相比用一个数组来记录，更省空间，并且代码量也少了。

【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "queue"
 5 using namespace std;
 6 char maz[25][25];
 7 int k, p, r, c;
 8 int a[15], b[15], cost[1<<11];
 9 const int dx[] = {0, 1, 0, -1};
10 const int dy[] = {-1, 0, 1, 0};
11 int sx, sy;
12 bool visit[25][25][1<<11];
13 
14 struct pos {
15     int x, y, cost, collect;
16     pos() {}//构造函数
17     pos(int a, int b, int c, int d) {
18         x = a, y = b, cost = c, collect = d;
19     }
20     bool operator< (const pos &a) const {
21         return cost > a.cost;
22     }
23 };
24 
25 bool check(int x, int y) {
26     return x >= 0 && x < r && y >= 0 && y < c;
27 }
28 
29 int bfs() {
30     priority_queue<pos> que;
31     memset(visit, false, sizeof(visit));
32     que.push(pos(sx, sy, 0, 0));
33     visit[sx][sy][0] = true;
34     while(!que.empty()) {
35         pos now = que.top();
36         que.pop();
37         int x = now.x, y = now.y, collect = now.collect, ncost = now.cost + cost[collect] + 1;
38         if(ncost > p) continue;
39         for(int i = 0; i < 4; i++) {
40             int nx = x + dx[i], ny = y + dy[i];
41             if(!check(nx, ny) || maz[nx][ny] == '#' || visit[nx][ny][collect]) continue;
42             if(nx == sx && ny == sy) {
43                 if(collect == (1 << k) - 1) return ncost;
44                 continue;
45             }
46             if(maz[nx][ny] <= 'Z' && maz[nx][ny] >= 'A') {
47                 int t = maz[nx][ny] - 'A';
48                 if((collect & (1 << t)) == 0) {
49                     que.push(pos(nx, ny, ncost + a[t], collect | (1<<t)));
50                     visit[nx][ny][collect|(1<<t)] = true;
51                 }
52             }
53             que.push(pos(nx, ny, ncost, collect));
54             visit[nx][ny][collect] = true;
55         }
56     }
57     return -1;
58 }
59 
60 int main() {
61     int T;
62     scanf("%d", &T);
63     while(T--) {
64         scanf("%d%d%d%d\n", &r, &c, &k, &p);
65         for(int i = 0; i < r; i++) {
66             for(int j = 0; j <= c; j++) {
67                 scanf("%c", &maz[i][j]);
68                 if(maz[i][j] == '*') sx = i, sy = j;
69             }
70         }
71         for(int i = 0; i < k; i++) scanf("%d%d", &a[i], &b[i]);
72         memset(cost, 0, sizeof(cost));
73         for(int t = 0; t < (1 << k); t++)
74             for(int j = 0; j < k; j++)
75                 if(t & (1 << j)) cost[t] += b[j];
76         int ans = bfs();
77         if(ans == -1) printf("Impossible\n");
78         else printf("%d\n", ans);
79     }
80     return 0;
81 }