#include #include #include #include using namespace std; const int MAXJ = 1000; const int MAXD = 5; const int INF = 10000000; struct vertex_info { int w; // vertex connected to int len; // edge length int ang; // angle edge leaves this vertex int vnum; // graph vertex # for this (vertex,ang) pair; }; struct vertex_input { int m; vertex_info edges[MAXD]; } input[MAXJ+1]; class edge { public: int dest; int len; edge *next; edge(int d, int l, edge* n=0) : dest(d), len(l), next(n) {} }; struct vertex { int baseNum; edge *list; bool visited; int dist; } graph[MAXJ*MAXD]; class pqEntry { public: int v; int dist; pqEntry(int iv, int d) : v(iv), dist(d) {} }; class mycomparison { public: bool operator() (const pqEntry& lhs, const pqEntry&rhs) const { return (lhs.dist > rhs.dist); } }; priority_queue, mycomparison> pq; void printGraph(int nV) { for(int i=0; inext) { cerr << " " << p->dest << "(" << p->len << ")"; } cerr << endl; } } void dijkstra(int src, int nV) { //cerr << "Dijkstras" << endl; for(int i=0; inext) { int w = p->dest; int dist = graph[e.v].dist + p->len; //cerr << " neighboring vertex " << w << ": curr dist = " << graph[w].dist << ", new dist = " << dist << endl; if (dist < graph[w].dist) { graph[w].dist = dist; pqEntry e2(w, dist); pq.push(e2); } } } } void addEdge(int v, int w, int len) { graph[v].list = new edge(w, len, graph[v].list); } int findVertexNum(int w, int v) { //cerr << " looking for vertex " << v << " in list of vertex " << w << endl; for(int j=0; j 360) ang1 -= 360; //cerr << " checking if angle " << ang2 << " is in range" << endl; int upper = ang1+d1; if (upper >= 360) upper -= 360; int lower = ang1-d2; if (lower < 0) lower += 360; if (upper > lower) return (ang2 <= upper && ang2 >= lower); else return (ang2 <= upper || ang2 >= lower); } int main() { int nVert, dest, a1, a2; cin >> nVert >> dest >> a1 >> a2; int vnum = 1; for(int i=1; i<=nVert; i++) { cin >> input[i].m; for(int j=0; j> input[i].edges[j].w >> input[i].edges[j].len >> input[i].edges[j].ang; input[i].edges[j].vnum = vnum++; } } // build graph for(int i=1; i<=nVert; i++) { vertex_input inp = input[i]; for(int j=0; j