388. Cheapest Route to the End
The edges carry weights now. Print the smallest total weight of any route from
vertex 1 to vertex n, or -1 if there is no route.
Breadth-first search is finished here, and it is worth seeing why rather than
being told. BFS finds the route with the FEWEST EDGES, which is the cheapest
route only when every edge costs the same. In the first sample the direct edge
1 → 4 is one hop and costs 10, while going the long way round costs 8. BFS
would answer 10.
The fix keeps the shape of BFS and changes the container. Instead of a queue handing back whatever arrived first, use a priority queue handing back the vertex with the smallest distance so far. Settle that vertex, relax its edges, and repeat. That is Dijkstra's algorithm.
Weights reach a million and there can be a hundred thousand edges, so a total can pass ten billion. That does not fit in a 32-bit integer.
Constraints - `1 ≤ n ≤ 100000` - `0 ≤ m ≤ 200000` - `1 ≤ w ≤ 1000000` - There are no self-loops and no repeated edges.
Input
The first line contains two integers n and m, the number of vertices and
edges. Each of the next m lines contains three integers u, v and w: an
undirected edge between those vertices whose weight is w. Vertices are
numbered 1 to n.
Output
Print one integer, the smallest total weight from vertex 1 to vertex n, or
-1 if vertex n cannot be reached.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.