decrypt_me's blog

By decrypt_me, history, 10 months ago, In English

Need Help! IN CSES Graph Series in Shortest Route 2 problem it is accepting solution of floyd warshall algorithm while O(n*2logn) not (using dijkastra Priority queue).

#

I want to know , when It is benificial to use floyd warshall algorithm and when not ?

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If $$$O(n^3)$$$ is allowed then it is very short to code floyd warshall. Also, floyd warshall works with negative edges too.

You can check this problem, which uses the idea used in floyd warshall.

Hint
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But in the question , it is given there is no negative weights. Thats why I am using priority queue. Thank you for suggestion and problem.