PROBLEM LINK:Author: Tuấn Anh Trần Đặng DIFFICULTY:Hard PREREQUISITES:Graph, Dynamic Programming ProblemGiven a weighted vertexcatus of N vertices answer Q queries about the shortest path between a pair of arbitrary vertices u and v. AssumptionsWe will mainly work on the DFS tree of the catus eg. performing DFS from 1 and only take the edges that connect a vertex to the unvisited vertex during the process. Subproblem 1Calculate the shortest path from 1 to every vertex u. SolutionLet’s call this d[u]. We can get d by doing a dynamic programming in the DFS process. When we visit u there are two situations:
Note that there are exactly two ways to go between two vertices in the same cycle C so the shortest path from top[C] to u is just either the distance L from top[C] to u in the DFS tree or length of cycle C  L. top[C] should be pre calculated. Subproblem 2Calculate the distance disTopDown(u, v) between u and one of it descendants v (in the DFS tree). Solution
So it seems like our solution is quite obvious now: distance between two vertices u and v is disTopDown(lca(u, v), u) + disTopDown(lac(u, v), v) where lca(u, v) is the lowest common ancester of u and v in the DFS tree. But we still missing one more piece: how to find b. Let get to the final subproblem. Subproblem 3We will make the problem a bit more genernal. Given the cycle C and the vertex v find the first vertex of C in the path from v to the root of the DFS tree. solutionHint: we can use the similar technique that we used in finding LCA. Order the cycle in the way that if cycle A lies on the path from root to cycle B then cycle A will get the larger order. One way is to use the order of the DFS completion of the top vertex eg. if the DFS process at top[B] finished later then B got larger order. Now you may already guessed the solution. We trying to go from v toward the top as far as possible making sure that we never enter the cycle C. Let order[C] is the order of cycle C we have to make sure that the maximum order of cycles that has a vertex in the path from v toward the root does not larger or equal to order[C]. Recall the problem of finding LCA, we have to prepare f[u][i] is the 2^i th parent of u. The formular is quite simple:
Apply the same technique let maxOrder[u][i] is the maximum label from u to its 2^ith parent:
With maxOrder calculated we try to jump from v toward the root and makesure that we never go a vertex with a order larger than or equal to order[C]. If b exist it will be the parent of the vertex we ended up at since we tried to go as close to C as possible but never enter it. SummaryThe solutions contains three part:
Complexity: O((N + M)logN) Author's/Tester's Solutions:
This question is marked "community wiki".
asked 18 Sep '16, 21:32

I was very disappointed solving that problem, it is very sad that in Codechef you are giving such wellknown and messy problem. For example, "BZOJ 2125" is the exactly the same problem. I had also seen a lot of variations of such problem. I'd love to see much more fresh problems here. answered 19 Sep '16, 02:22

my solution using dijkstra : output is ok.. but why it shows sigsev.. please tell ,, :) include<bits stdc++.h="">using namespace std; define max 20001define INF 100100vector<int>G[max]; vector<int>cost[max]; int d[max]; struct data {
}; void Dijkstra(int start,int node) { int i,j,u,v;
} int main() { int node,edge,i,j,k,l,m,x,y,z,start,end,cas;
}
link
This answer is marked "community wiki".
answered 20 Sep '16, 20:16

my solution using dijkstra .. output is ok.. but why it shows sigsev .. please anyne tell :) include<bits stdc++.h="">using namespace std; define max 200009define INF 300100vector<int>G[max]; vector<int>cost[max]; int d[max]; struct data {
}; int Dijkstra(int start,int node,int end) { int i,j,u,v;
} int main() { int node,edge,i,j,k,l,m,x,y,z,start,end,cas;
} answered 20 Sep '16, 20:20

Please move the problem to practice, the given link doesn't work.