题目大意：
有3个没有刻度的水壶，容量分别为a,b,c（均不超过200的正整数）。初始时候前两个水壶空，第三个装满了水。每次可以从一个水壶往另一个水壶倒水，直到其中一个水壶倒空或者另一个水壶倒满。为了使某个水壶恰好有d升水，至少要倒多少升的水？如果无解，则找一个小于且最接近于d的d'代替。
输出要求输出至少倒多少升水 和 d(d'）
思路：
把能达到的状态看成图上的点，进行BFS。
然后我用的是优先队列，能保证最少倒的条件。（按当前倒的水量维护好了）
建模确实不太好建。
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int MAXN=200+10;
const int INF=2000000;
bool vis[MAXN][MAXN][MAXN];
int state[3],d,ans;
struct node
{
int state[3];
int val;
node(){}
node(int aa,int bb,int cc,int dd){ state[0]=aa;state[1]=bb;state[2]=cc;val=dd;}
bool operator <(const node & x)const
{
return val>x.val;
}
};
void bfs()
{
memset(vis,0,sizeof(vis));
priority_queue<node> q;
q.push(node(0,0,state[2],0));
vis[0][0][state[2]]=true;
while(!q.empty())
{
node cur=q.top();
q.pop(); if(cur.state[0]==d || cur.state[1]==d || cur.state[2]==d)
{
ans=cur.val;
return;
} for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++) //j往i倒水
{
if(i==j) continue; //不能自己给自己倒水
if(!cur.state[j]) continue; //为空不行
node temp;
int *t=temp.state; //用指针优化下可读性 就是说t和temp.state是一个数组
if(cur.state[j] + cur.state[i] > state[i]) //超过了容量，只能倒满
{
t[i]=state[i];
t[j]=cur.state[j] + cur.state[i] -state[i];
t[3-i-j]=cur.state[3-i-j]; //3=0+1+2 所以减去代表剩下的那个
temp.val=cur.val+state[i] - cur.state[i];
}
else
{
t[i]=cur.state[j] + cur.state[i];
t[j]=0;
t[3-i-j]=cur.state[3-i-j];
temp.val=cur.val+cur.state[j];
}
if(!vis[ t[0] ][ t[1] ][ t[2] ]) //没访问过才加入队列
{
vis[ t[0] ][ t[1] ][ t[2] ]=true;
q.push(temp);
}
}
} }
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
ans=INF;
scanf("%d%d%d%d",&state[0],&state[1],&state[2],&d);
bfs();
while(ans==INF)
{
d--;
bfs();
}
printf("%d %d\n",ans,d);
}
return 0;
}