Graph Contest 3 P2 - Shortest Path

View as PDF

Submit solution

Points: 10 (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 (-100 \le c \le 1\,000) 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 \to 2 \to 3.


There are no comments at the moment.