Shortest PathGiven a directed graph, find the length of the shortest path from 1 to N.
InputN ≤ 1000, the number of vertices.
M ≤ 10000, 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.
OutputThe length of the shortest path from vertex 1 to vertex N.
3 3 1 2 1 2 3 2 1 3 5
Take the path 1-2-3.
Point Value: 10 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: Mar 04, 2009
- Graph Theory
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3