2456.cpp

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

/* This Code is Submitted by wywcgs for Problem 2456 on 2007-03-26 at 18:04:26 */
#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int PN = 128000;
const int CN = 6400;

class Point {
public:
	int x, y, z;
	void make() { scanf("%d %d %d", &x, &y, &z); }
	bool operator <(const Point& p) const { return x < p.x || (x == p.x && y < p.y) || (x == p.x && y == p.y && z < p.z); }
	bool operator !=(const Point& p) const { return p < *this || *this < p; }
	void print() { printf("%d %d %d ", x, y, z); }
};

class Edge {
public:
	Point a, b;
	void make(Point& pa, Point& pb) 
		{ a = pa; b = pb; if(b < a) swap(a, b); }
	bool operator <(const Edge&);
	void print() { a.print(); b.print(); printf("\n"); }
};
bool Edge::operator <(const Edge& e) {
	if(a != e.a) return a < e.a;
	else return b < e.b;
}

Edge e[PN];
Point p[24];

struct cmp {
	bool operator()(int a, int b) const
		{ return e[a] < e[b]; }
};

map<int, int, cmp> dict;
vector<int> g[CN];

int main()
{
	int cn;
	
	while(scanf("%d", &cn) != EOF && cn != 0) {
		dict.clear(); int tn = 0;
		for(int i = 0; i < cn; i++) {
			g[i].clear();
			int pn; scanf("%d", &pn);
			for(int j = 0; j < pn; j++) p[j].make();
			for(int j = 0; j < pn; j++) {
				e[tn].make(p[j], p[(j+1)%pn]);
				if(!dict.count(tn)) { dict[tn] = i; tn++; }
				else {
					int k = dict.find(tn)->second;
					g[k].push_back(i); g[i].push_back(k);
				}
			}
		}
		int m; scanf("%d", &m);
		int vst[CN], step[CN]; memset(vst, -1, sizeof(vst));
		for(int i = 0; i < m; i++) {
			int cs, ct; scanf("%d %d", &cs, &ct); cs--; ct--;
			queue<int> Q; Q.push(cs); step[cs] = 0; vst[cs] = i;
			while(!Q.empty()) {
				int no = Q.front(); Q.pop();
				for(int j = g[no].size()-1; j >= 0; j--) {
					int k = g[no][j];
					if(vst[k] == i) continue;
					vst[k] = i; Q.push(k); step[k] = step[no]+1;
				}
				if(vst[ct] == i) { printf("%d\n", step[ct]); break; }
			}
		}
	}
	
	return 0;
}