Mo_Huzaifa's blog

Need help to solve the problem
By Mo_Huzaifa, history, 2 years ago, In English

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

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

Comments Comments (1)
| Write comment?
»
2 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply