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

Need help to solve the problem
Автор Mo_Huzaifa, история, 23 месяца назад, По-английски

UCV2013B — Alice in Amsterdam, I mean Wonderland

This is a graph problem from spoj

Can anyone tell me how to solve it??

Link :https://www.spoj.com/problems/UCV2013B/

Thanks in advance

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

»
23 месяца назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Solve using Floyd-Warshall algorithm with a special case of containing a negative cycle.

https://cp-algorithms.com/graph/all-pair-shortest-path-floyd-warshall.html

If there exists a negative cycle, running the algorithm two times will produce lower distance than running it once (or as the blog says, the distance from a vertex to itself will be negative).

I advise you read the algorithm first, then handle the case with negative cycles.

→ Ответить