Shortest Path

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type

Given a directed graph, find the length of the shortest path from 1 to N.

Input Specification

N \le 1\,000, the number of vertices.
M \le 10\,000, the number of edges.
M lines, each with three integers a, b, c indicating a directed edge from a to b of length c.
Bonus: one case will have edges with negative lengths.
A shortest path will always exist.

Output Specification

The length of the shortest path from vertex 1 to vertex N.

Sample Input

3 3
1 2 1
2 3 2
1 3 5

Sample Output


Take the path 1-2-3.


There are no comments at the moment.