SPOJ-ROADS Dynamic programming problem

I’m trying to solve SPOJ-ROADS problem. Although i’m memorising the states correctly still, i’m getting unexpected TLE.
Plz help…

Code: https://ideone.com/BpFpHQ

Problem Link : http://www.spoj.com/problems/ROADS/

Thanks in advance!

1 Like

I also faced the same problem, so try using Dijkstra’s algorithm using a priority queue.
Link to my solution : Roads.cpp
Any doubts are welcome.