Hello CodeForces!
Recently, I was participating in a gym contest, and came across a very interesting graph problem.
For each vertice of given undirected weighted graph calculate the length of shortest simple cycle, which contains this vertice.
The graph does not contain self loops or multiple edges.
Here it is : http://codeforces.net/problemset/gymProblem/100917/F
After the contest, I did some googling, but I can only find re-search papers discussing very complex algorithms, I'm pretty sure the author did not intend these solutions.
My solution is as follows :
Let's say edge e connect vertices u and v. Remove edge e from the graph, then re-run dijikstra from u to v. If there exists a path, then there exists a simple cycle containing both u, and v.
Repeat for each edge, and minimise over the shortest cycle for each node.
The idea really makes sense, and the problem is the time limit verdict, how can I solve this problem more efficiently?
Please keep in mind that the graph is un-directed, ( the problem becomes easier in-case it is directed )
answer for node i is dp[i][i], where dp[i][j] = length of shortest path between nodes i and j
You can calculate this with floyd warhsall in O(n^3).
This does not work for un-directed graphs when searching for a simple cycle.
Floyd Warshall will just use each edge twice if it gives the minimum answer, thus the cycle is not simple.
That's why I said this version is much harder ( IMO at least, I'm pretty sure someone might come up with a mind blowing approach but still :D) than directed ones.
Maybe you'd also consider this a 'complex algorithm', but I just solved it in the following manner:
Code
Awesome!
Thanks a lot. I really appreciate that. This problem has been driving me crazy :D
Also, instead of preprocessing for LCA queries, you can store for each node the first node you saw on the shortest path to that node other than u with a small modification to Dijkstra's, and then check if those values are different instead of checking that the LCA is u.