P4011 孤岛营救问题

(color{#0066ff}{题目描述})

1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，迷宫地形复杂，但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形，其南北方向被划分为 (N) 行，东西方向被划分为 (M) 列，于是整个迷宫被划分为 (N imes M) 个单元。每一个单元的位置可用一个有序数对(单元的行号，单元的列号)来表示。南北或东西方向相邻的 (2) 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。迷宫中有一些单元存放着钥匙，并且所有的门被分成(P)类，打开同一类的门的钥匙相同，不同类门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角，即 ((N,M)) 单元里，并已经昏迷。迷宫只有一个入口，在西北角。也就是说，麦克可以直接进入 ((1,1)) 单元。另外，麦克从一个单元移动到另一个相邻单元的时间为 (1)，拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。

试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

(color{#0066ff}{输入格式})

第 (1) 行有 (3) 个整数，分别表示 (N,M,P) 的值。

第 (2) 行是 (1) 个整数 (K)，表示迷宫中门和墙的总数。

第 (I+2) 行((1leq Ileq K))，有 (5) 个整数，依次为(X_{i1},Y_{i1},X_{i2},Y_{i2},G_i) ：

• 当 (G_i geq 1G) 时，表示 ((X_{i1},Y_{i1})) 单元与 ((X_{i2},Y_{i2})) 单元之间有一扇第 (G_i) 类的门

• 当 (G_i=0) 时，表示 ((X_{i1},Y_{i1})) 单元与 ((X_{i2},Y_{i2})) 单元之间有一堵不可逾越的墙（其中，(|X_{i1}-X_{i2}|+|Y_{i1}-Y_{i2}|=1 ，0leq G_ileq P) ）。

第 (K+3) 行是一个整数 (S)，表示迷宫中存放的钥匙总数。

第 (K+3+J) 行((1leq Jleq S))，有 (3) 个整数，依次为 (X_{i1},Y_{i1},Q_i) ：表示第 (J) 把钥匙存放在 ((X_{i1},Y_{i1}))单元里，并且第 (J) 把钥匙是用来开启第 (Q_i) 类门的。（其中(1leq Q_ileq P) ）

输入数据中同一行各相邻整数之间用一个空格分隔。

(color{#0066ff}{输出格式})

将麦克营救到大兵瑞恩的最短时间的值输出。如果问题无解，则输出 -1。

(color{#0066ff}{输入样例})

4 4 9
9
1 2 1 3 2
1 2 2 2 0
2 1 2 2 0
2 1 3 1 0
2 3 3 3 0
2 4 3 4 1
3 2 3 3 0
3 3 4 3 0
4 3 4 4 0
2
2 1 2
4 2 1

(color{#0066ff}{输出样例})

14

(color{#0066ff}{数据范围与提示})

(∣X_{i1}−X_{i2}∣+∣Y_{i1}−Y_{i2}∣=1,0leq G_i leq P)

(1 leq Q_ileq P)
(N,M,Pleq10, K<150,Sleq 14)

(color{#0066ff}{题解})

这是网络流24题？？？？

裸的状压+搜索啊

连记忆化都不用18ms水过

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define _ 0
#define LL long long
inline LL in()
{
	LL x=0,f=1; char ch;
	while(!isdigit(ch=getchar()))(ch=='-')&&(f=-f);
	while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
	return x*f;
}
const int inf=0x7fffffff;
int rx[4]={-1,1,0,0};
int ry[4]={0,0,-1,1};
int mp[12][12][2048];
int tp[12][12][4];
int n,m,p,k,s;
std::vector<int> key[12][12];
inline int getdir(int s1,int s2,int t1,int t2)
{
	if(t1==s1-1) return 0;
	if(t1==s1+1) return 1;
	if(t2==s2-1) return 2;
	return 3;
}
inline void dfs(int x,int y,int zt)
{
	for(int i=0;i<=3;i++)
	{
		int xx=x+rx[i];
		int yy=y+ry[i];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m)
		{
			if(tp[x][y][i])
			{
				if(!(~tp[x][y][i])) continue;
				if(!(zt&(1<<(tp[x][y][i]-1)))) continue;
			}
			int now=zt;
			for(int v=0;v<(int)key[xx][yy].size();v++) now|=(1<<(key[xx][yy][v]-1));
			if(mp[xx][yy][now]>mp[x][y][zt]+1)
			{
				mp[xx][yy][now]=mp[x][y][zt]+1;
				dfs(xx,yy,now);
			}
		}
	}
}
int main()
{
	n=in(),m=in(),p=in(),k=in();
	int s1,s2,t1,t2,t,dir;
	for(int i=1;i<=k;i++)
	{	
		s1=in(),s2=in(),t1=in(),t2=in(),t=in();
		dir=getdir(s1,s2,t1,t2);
		t=t? t:-1;
		tp[s1][s2][dir]=t;
		tp[t1][t2][dir^1]=t;
	}
	s=in();
	for(int i=1;i<=s;i++)
	{
		s1=in(),s2=in(),t=in();
		key[s1][s2].push_back(t);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int v=0;v<(1<<p);v++)
				mp[i][j][v]=inf;
	int zt=0;
	for(int i=0;i<(int)key[1][1].size();i++) zt|=(1<<(key[1][1][i]-1));
	mp[1][1][zt]=0;
	dfs(1,1,zt);
	int min=inf;
	for(int i=0;i<(1<<p);i++) min=std::min(min,mp[n][m][i]);
	printf(min==inf? "-1":"%d",min);
	return 0;
}