Single Source Shortest Path

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 256M
Author:
FatalEagle
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Problem Description

Solve the Single Source Shortest Path problem.

Input Specification

Line 1: N (2 \le N \le 1\,000) (vertices), M (1 \le M \le 5\,000) (bidirectional edges)

Lines 2 to M+1: u_i, v_i, w_i (1 \le u_i, v_i \le N, 1 \le w_i \le 10\,000), a bidirectional edge from u_i to v_i with weight w_i. Multiple edges between the same pair of vertices may occur in the input.

Output Specification

Lines 1 to N: line i has the length of the shortest path from vertex 1 to vertex i. If no path exists, output -1.

Sample Input

4 3
1 2 2
1 3 5
2 3 2

Sample Output

0
2
4
-1

Comments


  • -6
    Winbigwok  commented on April 14, 2020, 9:01 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 9
      Kirito  commented on April 15, 2020, 2:49 a.m.


      • 2
        Winbigwok  commented on April 15, 2020, 7:27 p.m.

        thank you!


  • -7
    Winbigwok  commented on April 10, 2020, 6:37 a.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


  • 3
    yaxollum  commented on Feb. 5, 2019, 5:50 p.m.

    Is there something wrong with my implementations of Dijkstra's? How come Bellman-Ford is two times faster?


  • 2
    juho  commented on Jan. 24, 2018, 12:14 p.m.

    Can someone please tell me what is wrong with my c++ code? I just translated my Python Code, which passed with AC, into a c++ one, but it gets the majority of the cases wrong. Thanks in advance.


    • 6
      xiaowuc1  commented on Jan. 24, 2018, 1:08 p.m.

      Your C++ code is quite different from your Python code. Please reread the problem description.


      • 4
        juho  commented on Jan. 24, 2018, 5:14 p.m.

        I am actually dumb, I forgot that "Multiple edges between the same pair of vertices may occur in the input." Thanks for the reply.


  • -5
    haoda  commented on Feb. 25, 2017, 11:50 a.m. ← edited

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 12
      Xyene  commented on Feb. 25, 2017, 11:58 a.m.

      a bidirectional edge from u_i to v_i with weight w_i.

      So, undirected.


      • 4
        haoda  commented on Feb. 25, 2017, 12:05 p.m.

        thanks


  • -68
    moladan123  commented on Jan. 17, 2016, 2:57 p.m. ← edit 2

    This comment is hidden due to too much negative feedback. Click here to view it.