1641. Cheapest Route When Edges Can Pay You
A directed graph has weights that may be NEGATIVE. Print the smallest total
weight of any route from vertex 1 to vertex n.
Print -1 if no route exists, and negative cycle if the cost can be driven
down without limit.
Problem #388 solved this with Dijkstra, and Dijkstra is now wrong. It finalises the nearest unfinished vertex and never looks at it again, which is sound only because a non-negative edge can never make a finalised distance smaller. One negative edge and a vertex can be improved after it was declared finished, so Dijkstra returns a plausible wrong number rather than failing loudly.
Relax every edge instead, n - 1 times. A shortest path visits at most n
vertices and so uses at most n - 1 edges, and each pass fixes at least one
more edge of it.
Then relax once more. Anything that still improves is being fed by a cycle of
negative total weight, and if that improvement can reach n then no cheapest
route exists, because going round once more is always cheaper.
Constraints - `1 ≤ n ≤ 1000` - `0 ≤ m ≤ 5000` - `1 ≤ u, v ≤ n` - `-1000 ≤ w ≤ 1000`
Input
The first line contains two integers n and m.
Each of the next m lines contains three integers u, v and w: a directed edge from u to v of weight w.
Output
Print the smallest total weight from vertex 1 to vertex n, or -1 if there is no route, or negative cycle if the cost is unbounded below.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.