#include #define FOR(i, j, k, in) for (int i=j ; i=k ; i-=in) #define REP(i, j) FOR(i, 0, j, 1) #define RREP(i, j) RFOR(i, j, 0, 1) #define MOD 1000000007 #define INF 0x3f3f3f3f using namespace std; typedef pair iPair; vector parents(200, INF); vector dist(200, INF); int sI(){ register int c = getchar(); bool flag = true; if(c=='-'){ flag =false; c = getchar(); } int n = 0; for( ; (c<48 || c>57); c = getchar() ); for( ; (c>47 && c<58); c = getchar() ){ n = (n<<1) + (n<<3) +c -48; } if(flag){ return n; } else{ return n*-1; } } //vector parents(200, INF); // This class represents a directed graph using // adjacency list representation class Graph { int V; // No. of vertices // In a weighted graph, we need to store vertex // and weight pair for every edge list< pair > *adj; public: Graph(int V); // Constructor // function to add an edge to graph void addEdge(int u, int v, int w); // prints shortest path from s void shortestPath(int s); }; // Allocates memory for adjacency list Graph::Graph(int V) { this->V = V; adj = new list< pair >[V]; } void Graph::addEdge(int u, int v, int w) { adj[u].push_back(make_pair(v, w)); adj[v].push_back(make_pair(u, w)); } // Prints shortest paths from src to all other vertices void Graph::shortestPath(int src) { // Create a set to store vertices that are being // prerocessed set< pair > setds; // Create a vector for distances and initialize all // distances as infinite (INF) // Insert source itself in Set and initialize its // distance as 0. setds.insert(make_pair(0, src)); dist[src] = 0; /* Looping till all shortest distance are finalized then setds will become empty */ while (!setds.empty()) { // The first vertex in Set is the minimum distance // vertex, extract it from set. pair tmp = *(setds.begin()); setds.erase(setds.begin()); // vertex label is stored in second of pair (it // has to be done this way to keep the vertices // sorted distance (distance must be first item // in pair) int u = tmp.second; // 'i' is used to get all adjacent vertices of a vertex list< pair >::iterator i; for (i = adj[u].begin(); i != adj[u].end(); ++i) { // Get vertex label and weight of current adjacent // of u. int v = (*i).first; int weight = (*i).second; // If there is shorter path to v through u. if (dist[v] > dist[u] + weight) { /* If distance of v is not INF then it must be in our set, so removing it and inserting again with updated less distance. Note : We extract only those vertices from Set for which distance is finalized. So for them, we would never reach here. */ if (dist[v] != INF) setds.erase(setds.find(make_pair(dist[v], v))); // Updating distance of v dist[v] = dist[u] + weight; parents[v]=u; setds.insert(make_pair(dist[v], v)); } } } // Print shortest distances stored in dist[] /** printf("Vertex Distance from Source\n"); for (int i = 0; i < V; ++i) printf("%d \t\t %d\n", i, dist[i]); cout<<"\n\n\nthe parents are \n"; REP(i,V){ cout<0 && curr_y>1){ g.addEdge(curr_y*V+curr_x, (curr_y-2)*V+(curr_x-1), 300000); //cout<<"\n adding edge between "<1){ g.addEdge(curr_y*V+curr_x, (curr_y-2)*V+(curr_x+1), 300001); //cout<<"\n adding edge between "<0&&curr_y1){ g.addEdge(curr_y*V+curr_x, (curr_y)*V+(curr_x-2), 300005); //cout<<"\n adding edge between "< node_x && parent_y > node_y){ ans+="1"; } else if (parent_x < node_x && parent_y > node_y){ ans+="2"; } else if(parent_x > node_x && parent_y == node_y){ ans+="3"; } else if (parent_x < node_x && parent_y == node_y){ ans+="4"; } else if(parent_x < node_x && parent_y < node_y){ ans+="5"; } else if (parent_x > node_x && parent_y < node_y){ ans+="6"; } cnt++; node=parents[node]; //cout<