常州模拟赛d2t2 小X的密室
题目描述
密室中有 N 个房间,初始时,小 X 在 1 号房间,而出口在 N 号房间。
密室的每一个房间中可能有着一些钥匙和一些传送门,一个传送门会 单向地
创造一条从房间 X 到房间 Y 的通道。另外,想要通过某个传送门,就必须具备一
些种类的钥匙。幸运的是,钥匙在打开传送门的封印后,并不会消失。
然而,通过密室的传送门需要耗费大量的时间,因此,小 X 希望通过尽可能
少的传送门到达出口,你能告诉小 X 这个数值吗?
另外,小 X 有可能不能逃出这个密室,如果是这样,请输出“No Solution”。
输入输出格式
输入格式:
从文件 room.in 中读取数据。
第一行三个整数 N、M、K,分别表示房间的数量、传送门的数量以及钥匙的
种类数。
接下来 N 行,每行 K 个 0 或 1,若第 i 个数为 1,则表示该房间内有第 i 种
钥匙,若第 i 个数为 0,则表示该房间内没有第 i 种钥匙。
接下来 M 行,每行先读入两个整数 X,Y,表示该传送门是建立在 X 号房间,
通向 Y 号房间的,再读入 K 个 0 或 1,若第 i 个数为 1,则表示通过该传送门需
要 i 种钥匙,若第 i 个数为 0,则表示通过该传送门不需要第 i 种钥匙。
输出格式:
输出一行一个“No Solution”,或一个整数,表示最少通过的传送门数。
输入输出样例
3 3 2
1 0
0 1
0 0
1 3 1 1
1 2 1 0
2 3 1 1
2
说明
n <= 5000 m <= 6000 k <= 10
分析:本质上还是最短路,只是多了钥匙的限制,那么就要在状态的记录上和vis数组上花功夫,毕竟,我们总不能开一个10维数组来一个一个判断吧.
观察发现k非常小,而且有0/1性质:我们可以选或不选,而且只有这两种选择,那么可以很自然的想到状态压缩,利用二进制来维护信息.这个时候,检验能不能通过传送门i,则当前的钥匙状态sta & i 是不是等于i,到达一个房间后我们sta |= room[i]就好了,room[i]表示第i个房间的钥匙的状态数.
不过我打的是spfa,不是正确的解法,观察发现边权为1,这就是bfs!
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue> using namespace std; const int inf = 0x7ffffff; int n, m, k,room[],head[],to[],nextt[],tot = ,w[],d[],vis[][]; struct node
{
int x,sta;
}; void add(int x, int y, int z)
{
w[tot] = z;
to[tot] = y;
nextt[tot] = head[x];
head[x] = tot++;
} void spfa()
{
queue <node> q;
for (int i = ; i <= n; i++)
d[i] = inf;
d[] = ;
node temp;
temp.x = ;
temp.sta = room[];
vis[][room[]] = ;
q.push(temp);
while (!q.empty())
{
node u = q.front();
q.pop();
int x = u.x, sta = u.sta;
vis[x][sta] = ;
for (int i = head[x]; i; i = nextt[i])
{
if ((w[i] & sta) == w[i])
{
int v = to[i];
if (d[v] > d[x] + )
{
d[v] = d[x] + ;
int nsta = (sta | room[v]);
if (!vis[v][nsta])
{
vis[v][nsta] = ;
node t;
t.x = v;
t.sta = nsta;
q.push(t);
}
}
}
}
}
} int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = ; i <= n; i++)
{
int sta = ;
for (int j = ; j < k; j++)
{
int t;
scanf("%d", &t);
sta |= (t << j);
}
room[i] = sta;
}
for (int i = ; i <= m; i++)
{
int x, y, sta = ;
scanf("%d%d", &x, &y);
for (int j = ; j < k; j++)
{
int t;
scanf("%d", &t);
sta |= (t << j);
}
add(x, y, sta);
}
spfa();
if (d[n] == inf)
printf("No Solution");
else
printf("%d\n", d[n]); return ;
}
最新文章
- MySql - InnoDB - 事务 , Php版
- Spring MVC MultipartFile实现图片上传
- *HDU1847 博弈
- spring aop 环绕通知around和其他通知的区别
- 您还有心跳吗?超时机制分析(java)
- C#外挂QQ找茬辅助源码,早期开发
- POJ --- 3613 (K步最短路+矩阵快速幂+floyd)
- 基本数据类型的常量池与String类型常量池解析
- OC特有语法-分类(category)
- UITextField的属性设置
- <;转>;SQL的执行顺序
- [Angular Tutorial] 5-Filtering Repeaters
- 201521123110 《Java程序设计》第1周学习总结
- jquery获取value值时将数字型字符串前面的0自动截取处理方法
- Liunx find/locate/whereis/which 总结
- Koa 学习笔记
- Cobbler自动化批量安装Linux操作系统 - 运维总结
- Oracle用分区表分区交换做历史数据迁移
- js与ios桥接使用WebViewJavascriptBridge简单理解
- Go错误处理(二)