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

will modify dijsktra work for this problem ?
Автор Fear_Is_An_Illusion, история, 9 лет назад, По-английски

hello, in this sum question I have been trying to implement a modified dijsktra but fail. I just want to know if modified dijsktra work here.

please don't give further hints

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

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

I am not sure what you mean by modified Dijkstra,
but I did solve it with Dijkstra.

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

    thanks, i will try more .. modified dijsktra means it has slight modification .. okay sorry if it confuses

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

      Good luck :)

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

        so, earlier I was trying to just use some kind of hash to track the weights. but then I realised, I could just stotre the nodes of shortest path and take 2 consecutive nodes and mark the precomputed hashng of edges with those 2 vertices as true.. then just print indices of vertices which are false after getting all shortest paths..

        what did u do

        → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
          ← Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

          My solution doesn't have hashing actually.

          What I did was: do a All-Pairs Shortest Path by using Dijkstra V times.
          Then I enumerate through each edge, and see if the shortest path between any pairs of nodes pass that edge.

          The whole solution works in O(V3 + E * V2).
          The complexity is kind of lousy, but we have 8 minutes to work with.

          → Ответить