I was trying this problem.

problem description in short:

you are given a directed graph. You can go from node s to node t if the total cost(sum of costs of the edge we take) of the path is not greater than a given value , p. From this path we can take one edge cost. And our target is to maximise the cost of the edge(we have chosen).

My idea is to find shortest distance from s to every other node.

Then, find shortest distance from t to every other node to the inverse graph(this graph contain the reverse direction for every edge in the original graph).

Then for every edge, u-v we can take that edge if distance(s,u)+cost(u,v)+inverse_distance(t,v)<=p and we have to maximise the value of cost(u,v).

I got AC with Dijkstra(code). But getting WA with SPFA(code) mentioned in this blog. Ignore my bad implementation. I tried to debug this myself but failed. Again I have tried this. Am I doing something wrong in my SPFA ? Or something else?

Thanks in advance.