UVA - 658 It's not a Bug, it's a Feature! (隐式图的最短路,位运算)
2024-09-28 18:15:58
隐式的图搜索,存不下边,所以只有枚举转移就行了,因为bug的存在状态可以用二进制表示,转移的时候判断合法可以用位运算优化,
二进制pre[i][0]表示可以出现的bug,那么u&pre[i][0] == u就表示u是可以出现的bug集合的子集,
pre[i][1]表示必须出现的bug,那么u|pre[i][i] != u表示把必须出现的bug添加到u中,u中bug增加表面bug不全在u中,这是不合法的。
正权最短路就dijkstra,用spfa以前某题狂T有阴影。被输出格式坑得不要不要的,如果是if(kas) putchar('\n');就会WA...
#include<bits/stdc++.h>
using namespace std; const int maxm = ;
const int maxn = ; int pre[maxm][],nxt[maxm][];
int cost[maxm];
int n,m; int dist[<<maxn]; typedef pair<int,int> Node;
#define fi first
#define se second //bitset<20> temp;
#define bug(u)\
temp = u; cout<<#u<<'='<<temp<<endl;
#define cer(x)\
cout<<"dist="<<x<<endl; const int INF = 0x3f3f3f3f; void dijkstra()
{
priority_queue<Node,vector<Node>,greater<Node> > q;
memset(dist,0x3f,sizeof(int)*(<<n));
q.push(Node(,(<<n)-));
dist[(<<n)-] = ;
while(q.size()){
Node x = q.top(); q.pop();
if(x.se == ) { printf("Fastest sequence takes %d seconds.\n",dist[]); return; }
if(x.fi != dist[x.se]) continue;
int u = x.se;
for(int i = ; i < m; i++){
if( (pre[i][]&u) == u && (pre[i][]|u) == u){
int v = (u&nxt[i][])|nxt[i][];
if(dist[v] > dist[u]+cost[i]){
dist[v] = dist[u] + cost[i];
q.push(Node(dist[v],v));
}
}
}
}
puts("Bugs cannot be fixed.");
} int main()
{
//freopen("in.txt","r",stdin);
int kas = ;
char s1[maxn+],s2[maxn+];
while(scanf("%d%d",&n,&m),n){
for(int i = ; i < m ; i++){
scanf("%d%s%s",cost+i,s1,s2);
nxt[i][] = nxt[i][] = pre[i][] = pre[i][] = ;
for(int j = ; j < n; j++){
if(s1[j] == '+') pre[i][] |= <<j;
if(s1[j] != '-') pre[i][] |= <<j;
if(s2[j] == '+') nxt[i][] |= <<j;
if(s2[j] != '-') nxt[i][] |= <<j;
}
}
printf("Product %d\n",++kas);
dijkstra();
putchar('\n');
}
return ;
}
最新文章
- JavaScript 实现5秒倒计时,接着跳转
- HTML元素隐藏和显示
- es6 let
- Android SDK安装Android4.0“冰激淋三明治”(IceCreamSandwich)教程(转载)
- [转]发送邮件提示“551 User not local; please try ”错误的原因及解决办法
- {转自MC}NVIDIA DirectX 11演示DEMO详解
- Encoding 分类: HDU 2015-06-25 21:56 9人阅读 评论(0) 收藏
- 主成分分析(PCA)
- PF_RING 实验
- Visual Event插件----查看html元素绑定的事件与方法的利器
- Hibernate入门(2)- 不用配置用注解
- CodeForces Round #279 (Div.2)
- GCC编译警告和错误
- Codeforces 439 A. Devu, the Singer and Churu, the Joker
- Identity Card(水题)
- Java IO 文件与流基础
- 201521123008《Java程序设计》第六周实验总结
- 201521123019 《Java程序设计》第2周学习总结
- linux sudo 运行找不到java、python命令
- json模块
热门文章
- 20个Flutter实例视频教程-第08节: 保持页面状态
- Flutter实战视频-移动电商-35.列表页_上拉加载更多制作
- ASP.NET Core MVC 2.x 全面教程_汇总贴
- hql实现对表的某几个(部分)字段查询
- Bootstrap表格分页(二)
- 2016四川省赛A,C【写了1w个if的水题】
- shader实例(八)渲染路径RenderingPath
- VR头盔产品镜片评测
- MongoDb 安装服务 以及 安全配置
- ubuntu 14 安装XML::Simple 模块