2052.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2052 on 2006-07-08 at 16:17:40 */ 
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;

const int V = 5120;
const int CIRCLE = 360;
const int INF = 1 << 20;

class Point {
public:
	int log;
	set<int> cir;
	vector<int> nxt;
	void make() { scanf("%d", &log); cir.clear(); nxt.clear(); }
	int angle(const Point&) const;
};
int Point::angle(const Point& p) const {
	int k = abs(log-p.log), r = min(k, CIRCLE-k);
	if((log+r)%CIRCLE == p.log) return r;
	else return -r;
}

class Pair {
public:
	int a, b, c;
	Pair(int ca, int cb, int cc) : a(ca), b(cb), c(cc) {}
};

Point f[V];

int find(int);

int main()
{
	int v, e, i;
	
	while(scanf("%d %d", &v, &e) != EOF) {
		for(i = 0; i < v; i++) f[i].make();
		for(i = 0; i < e; i++) {
			int a, b; scanf("%d %d", &a, &b); a--; b--;
			f[a].nxt.push_back(b);
			f[b].nxt.push_back(a);
		}
		printf("%d\n", find(0));
	}
	
	return 0;
}

int find(int b)
{
	queue<Pair> Q;
	Q.push(Pair(b, 0, 0)); f[b].cir.insert(0);
	while(!Q.empty()) {
		Pair p = Q.front(); Q.pop();
		int o = p.a, ag = p.b, d = p.c, i;
		for(i = 0; i < f[o].nxt.size(); i++) {
			int no = f[o].nxt[i], nag = ag+f[o].angle(f[no]);
			if(f[no].cir.count(nag)) continue;
			else if(no == b) return d+1;
			Q.push(Pair(no, nag, d+1));
			f[no].cir.insert(nag);
		}
	}
	return -1;
}