题意：本题的题意是给你三个杯子，第一二个杯子是空的，第三个杯子装满水，要求是量出一定容量d升的水。若是得不到d升的水，那就让某一个杯子里面的水达到d‘，使得d'尽量接近d升。
解题思路：本题是给出初始状态，让你寻找一条通往目标的路径，此题也可看成是有向图中在起点和目标点之间寻找一条最短路径，但是这个最短路径不是距离最短而是倒的水最少，所以这题类似于Dijkstra算法求最短路，利用广搜，一直选当前水量最少的结点进行扩展，所以可以建立一个优先队列来存储下一次要访问的结点，同时将访问过的结点标记一下，大大节省了访问时间，此题的结点数最多为201^2.
代码：
1 #include<stdio.h> 2 #include<math.h> 3 #include<queue> 4 #include<string.h> 5 #include<iostream> 6 using namespace std; 7 const int maxn=205; 8 int n; 9 int visit[maxn][maxn],cap[3],ans[maxn]; 10 //三个数组分别表示标记是否访问过这种情况，三个容器的大小，以及得到对应的水需要倒水的体积 11 12 struct Node{ 13 int v[3],dist; 14 const bool operator < (Node s) const{ //优先队列重载运算符 15 return dist>s.dist; 16 } 17 }; 18 19 void update(Node t){ //更新倒水数 20 for(int i=0;i<3;i++){ 21 int s=t.v[i]; 22 if(ans[s]<0 || t.dist<ans[s]){ 23 ans[s]=t.dist; 24 } 25 } 26 } 27 28 void traver(int a,int b,int c,int d){ //遍历函数 29 priority_queue<Node> q; 30 memset(visit,0,sizeof(visit)); 31 memset(ans,-1,sizeof(ans)); 32 cap[0]=a; 33 cap[1]=b; 34 cap[2]=c; 35 Node s; 36 s.v[0]=0; 37 s.v[1]=0; 38 s.v[2]=c; 39 s.dist=0; 40 q.push(s); 41 visit[0][0]=1; 42 while(!q.empty()){ 43 Node t=q.top(); 44 q.pop(); 45 update(t); 46 if(ans[d]>=0) break; 47 for(int i=0;i<3;i++){//访问下一个结点,表示将水从i杯倒到j杯 48 for(int j=0;j<3;j++){ 49 if(i!=j){ 50 if(t.v[i]==0||t.v[j]==cap[j]) continue; 51 Node k; 52 int water=min(t.v[i],cap[j]-t.v[j]); 53 k.dist=t.dist+water; 54 k.v[i]=t.v[i]-water; 55 k.v[j]=t.v[j]+water; 56 k.v[3-i-j]=t.v[3-i-j]; //如果不是讲原结点复制过来的，记得给此结点赋值 57 if(!visit[k.v[0]][k.v[1]]){ 58 visit[k.v[0]][k.v[1]]=1; 59 q.push(k); 60 } 61 } 62 } 63 } 64 } 65 for(;d>=0;d--){ //输出 66 if(ans[d]>=0){ 67 printf("%d %d ",ans[d],d); 68 break; 69 } 70 } 71 } 72 73 int main(){ 74 freopen("in.txt","r",stdin); 75 scanf("%d",&n); 76 while(n--){ 77 int a,b,c,d; 78 scanf("%d%d%d%d",&a,&b,&c,&d); 79 traver(a,b,c,d); 80 } 81 return 0; 82 }