StandAlone1234's blog

Floyd Warshall help
By StandAlone1234, history, 4 years ago, In English

Can anybody help me with the problem? Floyd Warshall

Why one approach is wrong and one approach correct? Explanation with examples will be highly appreciated.

Code

Thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I have no idea how to interpret dp when you put k in the inner loop. In Floyd-Warshall, k represents the intermediate vertex, i.e., the algorithm updates dp when it finds a shorter path passing through k.

→ Reply
»
4 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

You can get correct answer if you run the incorrect FW 3 times. https://codeforces.me/blog/entry/89442 (Comments)

→ Reply