Блог пользователя MedoN11

Автор MedoN11, история, 9 лет назад, По-английски

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://mirror.codeforces.com/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 )

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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).

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +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.

»
9 лет назад, # |
Rev. 8   Проголосовать: нравится +5 Проголосовать: не нравится

Maybe you'd also consider this a 'complex algorithm', but I just solved it in the following manner:

  • Fix some node u.
  • Run Dijkstra's algorithm with source u, denote the distance of a vertex v to u as dv. If you store parents, this will give you a shortest-path tree rooted at u.
  • Preprocess the tree for LCA queries.
  • Consider some edge e = {v, x} that is not in the shortest-path tree. If lca(v, x) = u, then the path is a simple cycle containing u, with weight dv + dx + w(e). The answer for vertex u is the minimum weight over all such cycles.

Code

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Awesome!

    Thanks a lot. I really appreciate that. This problem has been driving me crazy :D

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    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.