Fill UVA - 10603（A*）

题目大意：
给你三个瓶子，并且给你他们的体积分别是a,b,c，但是一开始第一个和第二个杯子是空的，只有第三个是满的，然后给你一个d，问你通过许多次倒水使得其中一个水杯的体积为d，你倒的水的最小值是多少？
思路：
他求的是倒水的最小值，并不是倒水的最小次数，先把这个分清楚。
先把三个目前状态下的状态存储起来，然后每次选倒水量最小的（A*思路）损失函数G=水的量+到当前状态的水量。
用优先队列存储，可以实现每次取最小水量的元素，用一个一维数组ans[i]，表示某个水杯的容量i的步数，一开始设置为-1.
具体思路在代码里面，应该写的已经很清楚了。
代码：

#include<bits/stdc++.h>
using namespace std;const int maxn=1e3+10;
int ans[maxn];
int cap[3],vis[maxn][maxn];struct node{int dist;//步数 int v[3];//三个杯子目前存储的水 node(int a,int b,int c,int d){dist=a;v[0]=b;v[1]=c;v[2]=d;}node(){}bool operator<(const node &a)const {return dist>a.dist;}
};void uadate(node a){for(int i=0;i<3;i++){int t=a.v[i];if(ans[t]==-1||(ans[t]!=-1&&ans[t]>a.dist)){//修改每个容量的步数ans[t]=a.dist;}} 
}
void slove(int a,int b,int c,int d){priority_queue<node>st;memset(vis,0,sizeof(vis));memset(ans,-1,sizeof(ans));node s(0,0,0,c);cap[0]=a;cap[1]=b;cap[2]=c;st.push(s);while(!st.empty()){node now=st.top();st.pop();uadate(now);if(ans[d]>=0)break;//已经找到容量为d的杯子了for(int i=0;i<3;i++){//倒水的杯子 for(int j=0;j<3;j++){//被倒水的杯子 if(i!=j){//自己不能给自己倒水 if(now.v[i]==0||now.v[j]==cap[j])continue;//倒水的杯子没水，被倒水的杯子已经满了int water=min(cap[j],now.v[i]+now.v[j])-now.v[j];//求到了多少水 node tem;memcpy(&tem,&now,sizeof(now));tem.dist=now.dist+water; tem.v[j]+=water;tem.v[i]-=water;if(!vis[tem.v[0]][tem.v[1]]){vis[tem.v[0]][tem.v[1]]=1;st.push(tem) ;}}}}}while(d>=0){if(ans[d]>=0){cout<<ans[d]<<" "<<d<<endl;break;}d--;}
}
int main(){int T,a,b,c,d;scanf("%d",&T);while(T--){scanf("%d%d%d%d",&a,&b,&c,&d);slove(a,b,c,d);}}