Shortest Paths (Dijkstra, Bellman-Ford, Floyd-Warshall)
A country has n junctions numbered 1 to n and m two-way roads. Road i joins junctions u and v and takes w minutes to drive. Several roads may join the same pair of junctions, and a road may join a junction to itself. Find the minimum total driving time from junction 1 to junction n, or report that junction n cannot be reached.
The first line has n and m. Each of the next m lines has u, v and w.
Print one integer: the minimum number of minutes, or -1 if there is no route.
2 <= n <= 100000 0 <= m <= 200000 1 <= w <= 10^9 The answer can exceed 32 bits.
1000 ms256 MB
5 6 1 2 2 1 3 5 2 3 1 2 4 7 3 5 3 4 5 1
6
The best route is 1 to 2 (2), 2 to 3 (1), 3 to 5 (3): 6 minutes. Going 1-2-4-5 takes 10 and 1-3-5 takes 8.
3 1 1 2 4
-1
No road leads to junction 3.
