Today I was trying the problem POJ 1201 and when I searched for a solution I found out that every solution uses the same approach as this link: here
The article is not written in clear English so I couldn't understand it properly. Would anyone please help me understanding the trick in here and explain in a nice and simpler way? I think it's a very nice trick to relate equations with graph. Please help me. Thanks in advance :)
What you are looking for is System of difference constraints. It can be solved with bellman ford. SPFA Is short for Shortest Path Faster Algorithm which is just an optimized version of bellman ford that's much faster in practice.
https://www.google.com/search?q=system+of+difference+constraints
http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm
Thanks a lot :)