记录编号	334478	评测结果	AAAAA
题目名称	[CTSC 1999] 拯救大兵瑞恩	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2016-11-01 07:15:50	内存使用	3.63 MiB

#include "cstdio"
#include "cstring"
#include "queue"
using namespace std;

struct Edge
{
	int to, w, next;
	int rely;// 记录经过这条边需要的状态
}edges[5100];
int head[250], tot;
struct Node
{
	int pos, tot, type;
	inline Node(const int& a, const int& b, const int& c): pos(a), tot(b), type(c) {}
	inline bool operator < (const Node& a) const { return tot > a.tot; }
};
priority_queue <Node> Q;
int G[250][250];
int dis[250][1 << 12];
int n, m, p, k, S;
int key[250];// key[i]: 点i的钥匙情况

inline void AddEdge(const int& from, const int& to, const int& w, const int& rely)
{
	// printf("from:%d to:%d rely:%d\n", from, to, rely);
	edges[++tot].to = to;
	edges[tot].w = w;
	edges[tot].rely = rely;
	edges[tot].next = head[from];
	head[from] = tot;
}

inline int Change(const int& x, const int& y)
{
	return y + m * (x - 1);
}

inline void Dijkstra()
{
	memset(dis, 0x3f, sizeof dis);
	dis[1][key[1]] = 0; Q.push(Node(1, 0, key[1]));
	while (!Q.empty()) {
		Node top = Q.top(); Q.pop();
		int pos = top.pos, tot = top.tot, type = top.type;
		// printf("pos:%d tot:%d type:%d\n", pos, tot, type);
		if (tot != dis[pos][type]) continue;
		// if (pos == Change(n, m)) { printf("%d\n", dis[pos][type]); return; }
		for (int i = head[pos]; i; i = edges[i].next) {
			int to = edges[i].to, w = edges[i].w, rely = edges[i].rely;
			if ((type & rely) != rely) continue;
			if (dis[to][type|key[to]] > dis[pos][type] + w) {
				dis[to][type|key[to]] = dis[pos][type] + w;
				Q.push(Node(to, dis[to][type|key[to]], type|key[to]));
			}
		}
	}
	int ans = 0x3f3f3f3f;
	for (int i = 0; i <= (1 << p) - 1; ++i)
		ans = min(ans, dis[Change(n, m)][i]);
	if (ans != 0x3f3f3f3f) printf("%d\n", ans);
	else printf("-1\n");
}

#define SUBMIT
int main(int argc, char const *argv[])
{
#ifdef SUBMIT
	freopen("rescue.in", "r", stdin); freopen("rescue.out", "w", stdout);
#endif

	int x1, y1, x2, y2, type;
	scanf("%d%d%d", &n, &m, &p);
	scanf("%d", &k);
	while (k--) {
		scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &type);
		if (!type) {
			G[Change(x1, y1)][Change(x2, y2)] = -1;
			G[Change(x2, y2)][Change(x1, y1)] = -1;
		}
		if(type) {
			G[Change(x1, y1)][Change(x2, y2)] |= (1 << (type - 1));
			G[Change(x2, y2)][Change(x1, y1)] |= (1 << (type - 1));
		}
	}
	scanf("%d", &S);
	for (int i = 1; i <= S; ++i) {
		scanf("%d%d%d", &x1, &y1, &type);
		key[Change(x1, y1)] |= (1 << (type - 1));
	}
	for (int i = 1; i <= m * n; ++i) {
		if (i - m > 0 && G[i][i-m] >= 0) AddEdge(i, i-m, 1, G[i][i-m]);
		if (i + m <= m * n && G[i][i+m] >= 0) AddEdge(i, i+m, 1, G[i][i+m]);
		if (i - 1 && (i - 1 - 1) / m == (i - 1) / m && G[i][i-1] >= 0) AddEdge(i, i-1, 1, G[i][i-1]);
		if (i + 1 <= m * n && (i + 1 - 1) / m == (i - 1) / m && G[i][i+1] >= 0) AddEdge(i, i+1, 1, G[i][i+1]);
	}
	// printf("totedge:%d\n", tot);

	Dijkstra();

#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif

	return 0;
}