例题 7-8 倒水问题（Fill，UVa 10603）

本文主要是介绍例题 7-8 倒水问题（Fill，UVa 10603），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-10603
分类：优先队列
备注：状态图，Dijkstra算法

因为数据量小，所以比较简单。用一下优先队列就好。

#include<bits/stdc++.h>
using namespace std;
const int maxn=205;
const int inf=0x3f3f3f3f;
int vis[maxn][maxn];
struct node{int v[3],cost=0;bool operator < (const node& x) const{return cost>x.cost;}
};
int main(void){int T;int f[3],d;scanf("%d",&T);while(T--){scanf("%d %d %d %d",&f[0],&f[1],&f[2],&d);memset(vis,0,sizeof(vis));priority_queue<node>pq;node st;st.v[0]=st.v[1]=st.cost=0;st.v[2]=f[2];pq.push(st);int ans=0,dd=0,co=inf;while(!pq.empty()){node u = pq.top(); pq.pop();if(vis[u.v[0]][u.v[1]])continue;if(u.v[0]==d){ans=u.cost;dd=d;break;}if(u.v[1]==d){ans=u.cost;dd=d;break;}if(u.v[2]==d){ans=u.cost;dd=d;break;}for(int i=0;i<3;i++){if(u.v[i]<d&&u.v[i]>=dd){if(u.v[i]>dd){dd=u.v[i]; co=u.cost;}else{if(u.cost<co)co=u.cost;}}}vis[u.v[0]][u.v[1]]=1;for(int i=0;i<3;i++)for(int j=0;j<3;j++)if(i!=j){if(u.v[i]==0||f[j]==u.v[j])continue;int add=min(f[j]-u.v[j],u.v[i]);//要Pour多少水node nxt = u;nxt.cost+=add;nxt.v[j]=u.v[j]+add;nxt.v[i]=u.v[i]-add;pq.push(nxt);}           }if(dd!=d)ans=co;printf("%d %d\n",ans,dd);}return 0;
}

这篇关于例题 7-8 倒水问题（Fill，UVa 10603）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---