题意：本题的题意是给你三个杯子，第一二个杯子是空的，第三个杯子装满水，要求是量出一定容量d升的水。若是得不到d升的水，那就让某一个杯子里面的水达到d‘，使得d'尽量接近d升。
解题思路：本题是给出初始状态，让你寻找一条通往目标的路径，此题也可看成是有向图中在起点和目标点之间寻找一条最短路径，但是这个最短路径不是距离最短而是倒的水最少，所以这题类似于Dijkstra算法求最短路，利用广搜，一直选当前水量最少的结点进行扩展，所以可以建立一个优先队列来存储下一次要访问的结点，同时将访问过的结点标记一下，大大节省了访问时间，此题的结点数最多为201^2.
代码：
#include<stdio.h>
#include<math.h>
#include<queue>
#include<string.h>
#include<iostream>
using namespace std;
const int maxn=;
int n;
int visit[maxn][maxn],cap[],ans[maxn];
//三个数组分别表示标记是否访问过这种情况，三个容器的大小，以及得到对应的水需要倒水的体积 struct Node{
int v[],dist;
const bool operator < (Node s) const{ //优先队列重载运算符
return dist>s.dist;
}
}; void update(Node t){ //更新倒水数
for(int i=;i<;i++){
int s=t.v[i];
if(ans[s]< || t.dist<ans[s]){
ans[s]=t.dist;
}
}
} void traver(int a,int b,int c,int d){ //遍历函数
priority_queue<Node> q;
memset(visit,,sizeof(visit));
memset(ans,-,sizeof(ans));
cap[]=a;
cap[]=b;
cap[]=c;
Node s;
s.v[]=;
s.v[]=;
s.v[]=c;
s.dist=;
q.push(s);
visit[][]=;
while(!q.empty()){
Node t=q.top();
q.pop();
update(t);
if(ans[d]>=) break;
for(int i=;i<;i++){//访问下一个结点,表示将水从i杯倒到j杯
for(int j=;j<;j++){
if(i!=j){
if(t.v[i]==||t.v[j]==cap[j]) continue;
Node k;
int water=min(t.v[i],cap[j]-t.v[j]);
k.dist=t.dist+water;
k.v[i]=t.v[i]-water;
k.v[j]=t.v[j]+water;
k.v[-i-j]=t.v[-i-j]; //如果不是讲原结点复制过来的，记得给此结点赋值
if(!visit[k.v[]][k.v[]]){
visit[k.v[]][k.v[]]=;
q.push(k);
}
}
}
}
}
for(;d>=;d--){ //输出
if(ans[d]>=){
printf("%d %d\n",ans[d],d);
break;
}
}
} int main(){
freopen("in.txt","r",stdin);
scanf("%d",&n);
while(n--){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
traver(a,b,c,d);
}
return ;
}