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.
At line 14, It should be
type[ty][u] = 0;
thanks. done.