Single Source Shortest Path

View as PDF

Submit solution

All submissions

Best submissions

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 \leq N \leq 1 000)$ (vertices), $M$ $M$ $(1 \le M \le 5\,000)$ $(1 \leq M \leq 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)$ $(1 \leq u_{i}, v_{i} \leq N, 1 \leq w_{i} \leq 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

Copy

Sample Output

Copy

Comments

There are no comments at the moment.