Блог пользователя Draak_krijger_fanClub

Автор Draak_krijger_fanClub, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

At line 14, It should be type[ty][u] = 0;