1568.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1568 on 2006-07-07 at 23:49:25 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

enum { HUM, ROM, SHD };
const int LMT = 1000;
const int VN = 128;

class Vertex {
private:
	bool vst(int index) const { return (spd[index>>5]&(1<<(index&31))) != 0; }
	void set(int index) { spd[index>>5] |= 1 << (index&31); }
public:
	int k, l, u, spd[32];
	vector<int> nxt;
	void init(int);
	void clear() { memset(spd, 0, sizeof(spd)); }
	bool dfs(int, int);
};
Vertex v[VN];
void Vertex::init(int ck) {
	k = ck; nxt.clear();
	if(k == SHD) scanf("%d %d", &l, &u);
	else { l = 0; u = LMT; }
}
bool Vertex::dfs(int s, int ds) {
	if(s > LMT || s < 0) return false;
	else if(k == ROM) return true;
	else if(s > u || s < l || vst(s)) return false;
	int i, j; set(s);
	for(i = 0; i < nxt.size(); i++)
		for(j = -1; j <= 1; j++)
			if(k == HUM && j != 0) continue;
			else if(v[nxt[i]].dfs(s+ds*j, ds)) return true;
	return false;
}

int main()
{
	int t, T, i, j;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		int u, e; scanf("%d %d", &u, &e);
		for(i = 0; i < 3; i++) {
			int n; scanf("%*s %d", &n);
			for(j = 0; j < n; j++) {
				int a; scanf("%d", &a);
				v[a-1].init(i);
			}
		}
		scanf("%*s %d", &e);
		for(i = 0; i < e; i++) {
			int a, b; scanf("%d %d", &a, &b);
			v[a-1].nxt.push_back(b-1);
		}
		int b, cnt = 0; scanf("%*s %d", &b);
		for(i = 0; i < b; i++) {
			int c, s, ds; scanf("%d %d %d", &c, &s, &ds);
			for(j = 0; j < u; j++) v[j].clear();
			if(v[c-1].dfs(s, ds)) cnt++;
		}
		printf("%d\n", cnt);
	}
	
	return 0;
}