博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
UVA 10603 Fill(倒水,状态空间搜索)
阅读量:5248 次
发布时间:2019-06-14

本文共 1735 字,大约阅读时间需要 5 分钟。

#include
using namespace std;const int maxd = 200 + 5;int a, b, c, d;int vis[maxd][maxd];int ans[maxd];struct Node{ int x[3]; int dist; bool operator<(const Node& node)const{ return dist > node.dist; }};void update_ans(const Node& node){ for(int i = 0; i < 3; i++){ int x = node.x[i]; if(ans[x] < 0 || node.dist < ans[x]){ ans[x] = node.dist; } }}void solve(){ memset(ans, -1, sizeof(ans)); memset(vis, 0, sizeof(vis)); int cap[3] = {a, b, c}; Node start; start.x[0] = 0, start.x[1] = 0, start.x[2] = c; start.dist = 0; priority_queue
pq; pq.push(start); vis[0][0] = 1; while(!pq.empty()){ Node u = pq.top(); pq.pop(); update_ans(u); if(ans[d] >= 0){ break; } for(int i = 0; i < 3; i++){ for(int j = 0; j < 3; j++) if(i != j){ //if i -> i, it will get into dead loop //i->j if(u.x[i] == 0 || u.x[j] == cap[j]) continue; int amount = min(cap[j], u.x[i] + u.x[j]) - u.x[j]; Node v; memcpy(&v, &u, sizeof(u)); v.x[i] -= amount; v.x[j] += amount; v.dist = u.dist + amount; if(!vis[v.x[0]][v.x[1]]){ vis[v.x[0]][v.x[1]] = 1; pq.push(v); } } } } while(d >= 0){ if(ans[d] >= 0){ cout << ans[d] << ' ' << d << endl; return; } d--; }}int main(){ int T; cin >> T; while(T--){ cin >> a >> b >> c >> d; solve(); } return 0;}

 

转载于:https://www.cnblogs.com/sanshi-2018/p/10458900.html

你可能感兴趣的文章
【洛谷P1816 忠诚】线段树
查看>>
电子眼抓拍大解密
查看>>
poj 1331 Multiply
查看>>
tomcat7的数据库连接池tomcatjdbc的25个优势
查看>>
Html 小插件5 百度搜索代码2
查看>>
P1107 最大整数
查看>>
多进程与多线程的区别
查看>>
Ubuntu(虚拟机)下安装Qt5.5.1
查看>>
java.io.IOException: read failed, socket might closed or timeout, read ret: -1
查看>>
java 常用命令
查看>>
CodeForces Round #545 Div.2
查看>>
卷积中的参数
查看>>
51nod1076 (边双连通)
查看>>
Item 9: Avoid Conversion Operators in Your APIs(Effective C#)
查看>>
深入浅出JavaScript(2)—ECMAScript
查看>>
STEP2——《数据分析:企业的贤内助》重点摘要笔记(六)——数据描述
查看>>
ViewPager的onPageChangeListener里面的一些方法参数:
查看>>
Jenkins关闭、重启,Jenkins服务的启动、停止方法。
查看>>
CF E2 - Array and Segments (Hard version) (线段树)
查看>>
Linux SPI总线和设备驱动架构之四:SPI数据传输的队列化
查看>>