[CODEVS1911] 孤岛营救问题(分层图最短路)
2024-08-30 06:13:11
吐槽:神tm网络流。。。
用持有的钥匙分层,状态压缩,用 2 进制表示持有的钥匙集合。
dis[i][j][k] 表示持有的钥匙集合为 k,到达点 (i, j) 的最短路径。
分层图的最短路听上去很玄乎,其实通过代码来看还是很好理解的。
——代码
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 20
#define min(x, y) ((x) < (y) ? (x) : (y)) int n, m, p, ans = ~( << );
int map[N][N][N][N], key[N][N], dis[N][N][ << ];
int dx[] = {, , , -}, dy[] = {, , -, };
bool vis[N][N][ << ]; struct node
{
int x, y, s;
node(int x = , int y = , int s = ) : x(x), y(y), s(s) {}
}; std::queue <node> q; inline int read()
{
int x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline bool Acc(int x1, int y1, int x2, int y2, int s)
{
int need_key = map[x1][y1][x2][y2];
if(!need_key) return ;
if(need_key == -) return ;
return (s >> need_key - ) & ;
} inline void spfa()
{
node now;
int i, s, x, y;
memset(dis, / , sizeof(dis));
dis[][][] = ;
q.push(node(, , ));
while(!q.empty())
{
now = q.front();
q.pop();
vis[now.x][now.y][now.s] = ;
for(i = ; i < ; i++)
{
x = now.x + dx[i];
y = now.y + dy[i];
s = now.s | key[x][y];
if(!x || x > n || !y || y > m) continue;
if(Acc(now.x, now.y, x, y, now.s))
if(dis[x][y][s] > dis[now.x][now.y][now.s] + )
{
dis[x][y][s] = dis[now.x][now.y][now.s] + ;
if(!vis[x][y][s])
{
vis[x][y][s] = ;
q.push(node(x, y, s));
}
}
}
}
} int main()
{
int i, j, a, b, c, d, x, y, z, doors, keys;
n = read();
m = read();
p = read();
doors = read();
memset(map, -, sizeof(map));
for(i = ; i <= doors; i++)
{
a = read();
b = read();
c = read();
d = read();
map[a][b][c][d] = map[c][d][a][b] = read();
}
keys = read();
for(i = ; i <= keys; i++)
{
x = read();
y = read();
z = read();
key[x][y] |= << z - ;
}
spfa();
for(i = ; i < ( << ); i++) ans = min(ans, dis[n][m][i]);
if(ans == ) ans = -;
printf("%d\n", ans);
return ;
}
最新文章
- Windows平台Go调用DLL的坑
- PL/SQL设置快捷键
- ubuntu15.10跑裸机程序跑.bin文件
- hdu&#160;1162&#160;Eddy&#39;s&#160;picture(最小生成树,基础)
- Android中的音频播放(MediaPlayer和SoundPool)
- NGUI自适应分辨率,黑边自动填充, 无黑边,等比例缩放
- 每隔一段时间执行一次函数。window.setTimeout
- Kaggle入门——使用scikit-learn解决DigitRecognition问题
- nodejs+express+mongoose无法获取数据库数据问题解决
- windows下安装Python2和Python3共存
- NLP+VS=>;Image Caption︱自动生成图像标题技术论文+相关项目
- 第一个Polymer应用 - (0)准备工作
- 开源一个IE下获取XPath小工具,支持32/64位
- 第53章 结束会话端点(End Session Endpoint) - Identity Server 4 中文文档(v1.0.0)
- BZOJ2738 矩阵乘法(整体二分+树状数组)
- Redis常见业务场景应用
- QtWebkit包含的类简介
- BUG记忆
- PPI协议(西门子PLCS7-200)
- Ext之grid內編輯