1 #include<iostream>  2 #include<queue>  3 #include<string>  4 #include<cstring>  5 using namespace std;  6   7 int a, b, c, d;  8 int vis[205][205]; //访问变量，因为只有三个杯子，所以记录前两个杯子的状态即可  9 int cap[3]; 10 int ans[205]; 11  12 struct Node 13 { 14     int v[3], dist; 15     bool operator <(const Node& rhs) const //重载小于号 16     { 17         return dist>rhs.dist; 18     } 19 }; 20  21 void update(Node u)  //每次有新状态时，记录形成d升水时需要的最少倒水量 22 { 23     for (int i = 0; i < 3; i++) 24     { 25         int x = u.v[i]; 26         if (ans[x] < 0 || u.dist < ans[x])    ans[x] = u.dist; 27     } 28 } 29  30 void bfs() 31 { 32     cap[0] = a, cap[1] = b, cap[2] = c; //记录三个杯子的容量 33     memset(vis, 0, sizeof(vis)); 34     memset(ans, -1, sizeof(ans)); 35     priority_queue<Node> q; 36     Node start; 37     start.v[0] = 0; start.v[1] = 0; start.v[2] = c; start.dist = 0; 38     q.push(start); 39     vis[0][0] = 1; //设置初始状态为已访问 40     while (!q.empty()) 41     { 42         Node p = q.top(); 43         q.pop(); 44  45         update(p); 46         if (ans[d] >= 0) break;  //找到目标状态，退出循环 47  48         for (int i = 0; i < 3; i++) 49         { 50             for (int j = 0; j < 3; j++) 51             { 52  53                 if (i != j && p.v[i]!=0 && p.v[j]<cap[j]) //不能给自己倒水并且第i个杯子有水和第j个杯子未满 54                 { 55                     Node u=p; //建立新状态 56                     int r = cap[j] - p.v[j];  //计算第j个杯子空余水量 57                     if (p.v[i] >= r) //如果第i个杯子水量充足 58                     { 59                         u.dist = p.dist + r;  //更新后的倒水量 60                         u.v[j] = p.v[j] + r; //更新后第j个杯子水量 61                         u.v[i] = p.v[i] - r; //更新后第i个杯子水量 62                     } 63                     else //如果第i个杯子水量不足 64                     { 65                         u.dist = p.dist + p.v[i]; 66                         u.v[j] = p.v[j] + p.v[i]; 67                         u.v[i] = 0; 68                     } 69                     if(!vis[u.v[0]][u.v[1]]) //如果该状态没出现过 70                     { 71                        vis[u.v[0]][u.v[1]] = 1; 72                        q.push(u); 73                     } 74                 } 75  76  77             } 78         } 79  80     } 81  82     while (d >= 0) 83     { 84         if (ans[d] >= 0) 85         { 86             cout << ans[d] << " " << d << endl; 87             return;         88         } 89         d--; //如果无法做到d升，则检验d--，找到最接近d升 90     } 91 } 92  93 int main() 94 { 95     //freopen("D:\\txt.txt","r", stdin); 96     int n; 97     cin >> n; 98     while (n--) 99     {100         cin >> a >> b >> c >> d;101         bfs();102     }103     return 0;104 }