Shortest Path

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

Input

N ≤ 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.

Output

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

3

Take the path 1-2-3.

All Submissions
Best Solutions


Point Value: 10 (partial)
Time Limit: 1.00s
Memory Limit: 32M
Added: Mar 04, 2009

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I've used both the bellman ford and spfa algorithms? They should handle negative edge weights...

I've tried multiple algorithms, but I keep getting the last test case incorrect. What am I missing?

Bonus: one case will have edges with negative lengths.

My code worked fine on windows cmd but I'm getting RE for all test cases?
Are N and M on the same line separated by a space or on different lines?

N and M will be on the same line.

Here's your error:

Traceback (most recent call last): 
File "a.out", line 19, in <module>
graph[int(a[0])].append(weight)
KeyError: 3

For example:
3 3
1 2 1
2 1 -2
1 3 5

AFAIK there are no such cases in the actual test data