Given a cost matrix (may contain negative values) and a man has some non-negative initial strength, he starts from zero(start) position and complete his journey at (n-1)th position with some non-negative power. matrix[i][j]>0 denotes he lost his strength from moving city i to j and matrix[i][j]<0 denotes he gain his strength by matrix[i][j]. he has to cover all the cities from 1 to n-2 and during his journey path his power may become negative but at the (n-1)th pos(destination) his power must be non-negative. we have to find whether he able to complete his journey or not.
test case-
initial strength=1
cost matrix = [0 2 2 -1]
[4 0 2 -1]
[4 2 0 -1]
[4 2 2 0]
ans=YES
path is-
(0 -> 3 -> 1 -> 3 -> 2 -> 3)
strength during its journey
(1 -> 2 -> 0 -> 1 -> -1 ->0)
i have no idea how to solve this question please help.