Ra1nWarden
commented
9 years ago TC: 5 0 1 2 -60 1 3 -60 1 4 20 1 5 0 0 5 0 1 2 20 1 3 -60 1 4 -60 1 5 0 0 5 0 1 2 21 1 3 -60 1 4 -60 1 5 0 0 5 0 1 2 20 2 1 3 -60 1 4 -60 1 5 0 0 7 0 1 2 -98 2 3 5 -1 1 4 101 1 1 -60 1 6 -60 1 7 0 0 8 0 1 2 0 1 3 -5 1 4 -50 1 5 -40 2 6 7 110 1 3 0 1 8 0 0 1 0 0
7 0 2 2 6 -60 1 3 100 1 4 100 1 5 100 1 2 -120 1 7 0 0
-1
Bellman Ford algorithm run on opposite of the edges. Got WA and there are known corner cases: if relaxing an edge results in a weight more than 100, shall I relax it? Check negative cycle and then make sure that cycle can be reached by the start and can reach the end before printing "winnable"