Single Source Shortest Path

Points: 7

Time limit: 1.0s

Memory limit: 256M

Author:

FatalEagle

Problem type

Solve the Single Source Shortest Path problem.

Input Specification

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

Lines $2$ ~2~ to $M+1$ ~M+1~: $u_i, v_i, w_i$ ~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$ ~u_i~ to $v_i$ ~v_i~ with weight $w_i$ ~w_i~. Multiple edges between the same pair of vertices may occur in the input.

Output Specification

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

Sample Input

Sample Output

Comments

-1

User commented on Jan. 8, 2023, 7:45 a.m. ← edit 2 →

Aside from the TLEs can anyone find out why my code is giving blatantly wrong answers? I don't seriously expect to be able to fix the TLEs but I just want this program to give correct answers.

Nevermind, I forgot about the overlapping edges or whatever.

3

Winbigwok commented on April 15, 2020, 1:01 a.m.

Like how are the nodes linked?

30

Kirito commented on April 15, 2020, 6:49 a.m.

11

Winbigwok commented on April 15, 2020, 11:27 p.m.

thank you!

4

AussieSeaweed commented on Jan. 24, 2018, 5: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.

9

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

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

6

AussieSeaweed commented on Jan. 24, 2018, 10: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.

-18

haoda commented on Feb. 25, 2017, 4:50 p.m. ← edited →

.

This comment is hidden due to too much negative feedback. Show it anyway.

22

Xyene commented on Feb. 25, 2017, 4:58 p.m.

a bidirectional edge from $u_i$ ~u_i~ to $v_i$ ~v_i~ with weight $w_i$ ~w_i~.

So, undirected.

8

haoda commented on Feb. 25, 2017, 5:05 p.m.

thanks