先吐槽下这两天无限卡题，已经积了3道了。一筹莫展，只能先开一道稍微简单点的。
题意：这题就是加强版的倒水问题，把三个杯子分别含水量作为状态，已经倒水的值作为距离。构建隐式图，然后利用优先队列宽搜其中记得时刻更新到达终点的最小距离。因为有可能无法到达目标状态需要输出离目标最近的。其实状态还可进一步简化，由于总的水量是一定的，所以只要记录两个杯子的含水量就可推出第三个。我这里没有简化，代码也写得比较长。。。terrible。不过至少1A了
代码如下：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstring> 6 #include <algorithm> 7 #include <queue> 8 #include <stack> 9 #include <vector> 10 #define MP(a, b) make_pair(a, b) 11 #define PB(a) push_back(a) 12 13 using namespace std; 14 15 typedef long long ll; 16 typedef pair<int ,int> pii; 17 typedef pair<unsigned int, unsigned int> puu; 18 typedef pair<int ,double> pid; 19 typedef pair<ll, int> pli; 20 21 const int INF = 0x3f3f3f3f; 22 const double eps = 1e-6; 23 const int LEN = 201; 24 25 struct S{int a[3];}; 26 typedef pair<int, S> pis; 27 int ed, dis[LEN][LEN][LEN]; 28 bool vis[LEN][LEN][LEN]; 29 S st; 30 31 inline void setd(S &vex, int val){dis[vex.a[0]][vex.a[1]][vex.a[2]] = val;} 32 inline int getd(S vex){return dis[vex.a[0]][vex.a[1]][vex.a[2]];} 33 inline void svis(S vex){vis[vex.a[0]][vex.a[1]][vex.a[2]] = 1;} 34 inline bool isvis(S vex){return vis[vex.a[0]][vex.a[1]][vex.a[2]]==true;} 35 inline int cv(int val){return val>0?val:INF;} 36 struct cmp 37 { 38 bool operator()(pis x, pis y){return x.first > y.first;} 39 }; 40 41 //将水从a倒到b中 42 S pour(S vex, int a, int b, int &val) 43 { 44 int rest = st.a[b]-vex.a[b], water = vex.a[a]; 45 if(water>rest){ 46 vex.a[b] = st.a[b]; 47 vex.a[a]-=rest; 48 }else{ 49 vex.a[b]+=water; 50 vex.a[a] = 0; 51 } 52 val = min(water, rest); 53 return vex; 54 } 55 56 57 void BFS(S s) 58 { 59 priority_queue<pis, vector<pis>, cmp> q; 60 int y, mindip = INF, mp[3]; 61 memset(dis, 0x3f, sizeof dis); 62 memset(vis, 0, sizeof vis); 63 setd(s, 0); 64 q.push(MP(getd(s), s)); 65 svis(s); 66 while(!q.empty()){ 67 pis nvex = q.top(); q.pop(); 68 S nv = nvex.second; 69 if(nv.a[0]==ed || nv.a[1]==ed || nv.a[2]==ed){ 70 printf("%d %d ", getd(nv), ed); 71 return ; 72 } 73 if(min(cv(ed-nv.a[0]), min(cv(ed-nv.a[1]),cv(ed-nv.a[2])))<mindip){ 74 mindip = min(cv(ed-nv.a[0]), min(cv(ed-nv.a[1]),cv(ed-nv.a[2]))); 75 for(int i=0; i<3; i++)mp[i] = nv.a[i]; 76 } 77 for(int i=0; i<3; i++) 78 for(int j=0; j<3; j++){ 79 if(i==j || !nv.a[i])continue; 80 S av = pour(nv, i, j, y); 81 if(!isvis(av)){ 82 svis(av); 83 setd(av, getd(nv)+y); 84 q.push(MP(getd(av), av)); 85 } 86 } 87 } 88 printf("%d %d ", dis[mp[0]][mp[1]][mp[2]], ed-mindip); 89 } 90 91 int main() 92 { 93 // freopen("in.txt", "r", stdin); 94 95 int T; 96 scanf("%d", &T); 97 while(T--){ 98 for(int i=0; i<3; i++) scanf("%d", &st.a[i]); 99 scanf("%d", &ed); 100 BFS((S){0,0,st.a[2]}); 101 } 102 return 0; 103 }