Good day! I'm interested in the solution of the following problem via Ford-Bellman algorithm, because I only solved the one via Dijkstra. But my solution was not enough successful (4 tests of 13 passed).
Statement of the problem:
Any suggestion?
UPD I fixed error in my solution and it is Dijkstra with potentials now. After submitting, 13 tests of 13 are passed, but it work about 0.8 sec on the gentest.
Thus, the question of better solution is still open.
So, why don't you subtract 500 from length of every edge? It's not correct to subtract it only in the end because you don't know the length of the shortest path in advance.
Let me give an example: say you have found a path with length 3000 with 5 edges. So you output 3000 — 5 * 500 = 500. But if there exists a path with length 3200 with 6 edges, it would give 3200 — 6 * 500 = 200. Which is better. But you only find the first one because without the subtracted 500 from every edge it is shorter.