PEG Judge - Shortest Path

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

Sample Output

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)

ZorvyY on Jan 02, 2018 - 2:48:14 am UTC Re: What am I doing wrong?

(0/0)

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

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

ZorvyY on Jan 01, 2018 - 3:37:55 pm UTC What am I doing wrong?

(0/0)

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

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

jargon on Jan 01, 2018 - 8:35:56 pm UTC Re: What am I doing wrong?

(0/0)

[quote]Bonus: one case will have edges with negative lengths.[/quote]

Bonus: one case will have edges with negative lengths.

Chinadoll on Feb 17, 2017 - 11:15:16 pm UTC RE

(0/0)

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?

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?

jargon on Feb 18, 2017 - 10:30:44 pm UTC Re: RE

(0/0)

N and M will be on the same line.

Here's your error:

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

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

B on Oct 13, 2013 - 3:06:04 am UTC Infinitely short paths.

(0/0)

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

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

bbi5291 on Oct 13, 2013 - 3:33:54 am UTC Re: Infinitely short paths.

(0/0)

AFAIK there are no such cases in the actual test data

AFAIK there are no such cases in the actual test data