学步园

看了书上的解法，自己写了一遍，几乎没遇到什么障碍。不过看Board上面的讨论，觉得细节上需要注意的地方还是挺多的。。纯粹自己写肯定分分钟跪下

1、vis数组只用开两维

看到讨论中大家都是用的三维数组vis[201][201][201]，其实有了两杯水的数据，第三杯水可以用总量减去两杯水的量得到，所以不需要维护3维数组

2、解的存储

因为题目说如果取不到d，就要打印出比d小的最大的可能解d'以及倒水的量，所以bfs就把所有可能的d以及倒水量都存了下来，如果之前取到过这个d，则判断倒水量是否比之前的少，如果满足要求的话就更新数据。最后从d开始往下减小，遇到第一个取到过的解就打印并返回

3、优先队列

首先要注意这道题问的是倒水量最少，而不是倒水次数最少，而这两者没有必然关系。所以在bfs的时候，就不能用普通queue存储需要遍历的节点，而应该用一个优先队列，让倒水量少的排在前头。

另外在讨论中看到很多人用的是dfs，并且很多人得了TLE。然后大家比较推荐的解法是dijkstra。

Run Time: 0.142s

#define UVa  "LT7-8.10603.cpp"

#include<cstring>
#include<cstdlib>
#include<cstdio>

#include<queue>

#define maxn 500

using namespace std;

struct Node {
    int v[3], dist;
    bool operator < (const Node& n) const {
        return dist > n.dist;
    }
};

//Global Variables.
int vis[maxn][maxn];
int ans[maxn];
/////


void update_ans(Node& u) {
    for(int i = 0; i < 3; i ++) {
        int d = u.v[i];
        if(ans[d] < 0 || u.dist < ans[d])  ans[d] = u.dist;
    }
}

void solve(int a, int b, int c, int d) {
    int cap[3] = {a,b,c};
    memset(vis, 0, sizeof(vis));
    memset(ans, -1, sizeof(ans));

    Node startN;
    startN.v[0] = startN.v[1] = 0;
    startN.v[2] = c;
    startN.dist = 0;
    priority_queue<Node> q;
    q.push(startN);
    vis[0][0] = 1;
    while(!q.empty()) {
        Node u = q.top(); q.pop();
        update_ans(u);
        for(int i = 0; i < 3; i ++) {
            for(int j = 0; j < 3; j ++) if(i != j) {
                if(u.v[j] == cap[j] || u.v[i] == 0) continue;           //Empty / Full
                int amount = min(cap[j] - u.v[j], u.v[i]);              //Amount of water to fill
                Node newN;
                memcpy(&newN, &u, sizeof(u));
                newN.v[i] = u.v[i] - amount;
                newN.v[j] = u.v[j] + amount;
                newN.dist = u.dist + amount;
                if(!vis[newN.v[0]][newN.v[1]]) {
                    q.push(newN);
                    vis[newN.v[0]][newN.v[1]] = 1;
                }
            }
        }
    }

    while(d>=0) {          //print ans
        if(ans[d] >= 0) {
            printf("%d %d\n", ans[d], d);
            return;
        }
        d--;
    }
}

int main() {
    int kase;
    scanf("%d", &kase);
    while(kase--) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        solve(a, b, c, d);
    }
    return 0;
}