记录编号	179671	评测结果	AAAAA
题目名称	[CTSC 1999] 拯救大兵瑞恩	最终得分	100
用户昵称	lyxin65	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2015-08-17 01:17:24	内存使用	7.56 MiB

#include <bits/stdc++.h>
using namespace std;

#define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int, int> pii;

inline int read()
{
	int x = 0; int v = 1, c = getchar();
	for(; c < '0' || c > '9'; c = getchar()) if(c == '-') v = -1;
	for(;c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
	return x * v;
}
inline void write(LL x, int ch = 10)
{
	int s[20], t = 0;
	if(x < 0) { x = -x; putchar('-'); }
	do s[t++] = x % 10; while(x /= 10);
	while(t--) putchar('0' + s[t]);
	putchar(ch);
}

const int dx[] = {1, 0, 0, -1};
const int dy[] = {0, 1, -1, 0};
const int qsize = 1024 * 16 * 16 + 5;
const int oo = 0x3f3f3f3f;

#define inc(x) ++x >= qsize ? x = 0 : 0
#define dec(x) --x < 0 ? x += qsize : 0

struct Node
{
	int z, x, y;
};

int n, m, p, k, ss, ppfish, h, r;
int Right[17][17];
int down[17][17];
int key[17][17];
Node q[qsize];
bool inq[1025][17][17];
int dis[1025][17][17];

void input()
{
	n = read(); m = read(); p = read();
	k = read(); ppfish = 1 << p;
	for(int i = 1; i <= k; ++i) {
		int a = read(), b = read();
		int c = read(), d = read();
		int g = read();
		if(a == c) {
			int e = min(b, d);
			g ? Right[a][e] |= 1 << g-1 : Right[a][e] = -1;
		} else {
			int e = min(a, c);
			g ? down[e][b] |= 1 << g-1 : down[e][b] = -1;
		}
	}
	ss = read();
	for(int i = 0; i < ss; ++i) {
		int a = read(), b = read();
		key[a][b] |= (1 << read()-1);
	}
}
inline void pb(int z, int x, int y)
{
	inq[z][x][y] = 1; q[r] = (Node){z, x, y}; inc(r);
}
inline void pf(int z, int x, int y)
{
	inq[z][x][y] = 1; dec(h); q[h] = (Node){z, x, y};
}
inline void push(int z, int x, int y)
{
	dis[z][x][y] < dis[q[h].z][q[h].x][q[h].y] ? pf(z, x, y) : pb(z, x, y);
}
inline void pop(Node &res)
{
	res = q[h]; inc(h);
	inq[res.z][res.x][res.y] = 0;
}
void solve()
{
	memset(dis, oo, sizeof(dis));
	
	dis[0][1][1] = 0;
	pb(0, 1, 1);
	
	while(h != r) {
		Node now;
		pop(now);
		int z = now.z | key[now.x][now.y];
		int tmp = dis[now.z][now.x][now.y] + 1;
		for(int i = 0; i < 4; ++i) {
			int x = now.x + dx[i];
			int y = now.y + dy[i];
			if(x < 1 || x > n || y < 1 || y > m) continue;
			if(dis[z][x][y] <= tmp) continue;
			
			bool ok = 0;
			if(i == 0 && ~down[now.x][now.y] && (down[now.x][now.y] & z) == down[now.x][now.y]) ok = 1;
			if(i == 1 && ~Right[now.x][now.y] && (Right[now.x][now.y] & z) == Right[now.x][now.y]) ok = 1;
			if(i == 2 && ~Right[x][y] && (Right[x][y] & z) == Right[x][y]) ok = 1;
			if(i == 3 && ~down[x][y] && (down[x][y] & z) == down[x][y]) ok = 1;
			
			if(ok) {
				dis[z][x][y] = tmp;
				if(!inq[z][x][y]) push(z, x, y);
			}
		}
	}
	
	int ans = oo;
	for(int i = 0; i < ppfish; ++i)
		ans = min(ans, dis[i][n][m]);
	if(ans == oo) ans = -1;
	write(ans);
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("rescue.in", "r", stdin);
	freopen("rescue.out", "w", stdout);
#endif
	
	input();
	solve();
	
#ifndef ONLINE_JUDGE
	fclose(stdin), fclose(stdout);
#endif
	return 0;
}