314. Shortest Paths
Time limit per test: 0.25
second(s)
Memory limit: 65536
kilobytes
input: standard
output: standard
You are given a graph with one vertex marked as source
s and one as destination
t. Each edge of the graph has a positive length. Find the shortest path from
s to
t. Then find the secondshortest path (the shortest one of all the paths from
s to
t except the one you've just found). Then the thirdshortest, and so on. Output the lengths of first
k such paths.
Note that these paths may not be simple, i.e. they may contain some vertex or edge several times (see the 2nd example).
Input
The first line of the input file contains
n, the number of vertices of the graph,
m, the number of edges of the graph, and
k, the number of paths sought (2 ≤
n ≤ 10000, 2 ≤
m ≤ 50000, 2 ≤
k ≤ 10000).
The second line of the input file contains
s and
t (integers between 1 and
n, inclusive,
s !=
t).
The next
m lines contain the descriptions of the edges, each description consisting of three integer numbers:
a b c, denoting the edge from
a to
b with length
c (1 ≤
a,
b ≤
n,
a !=
b, 1 ≤
c ≤ 1000). There may be more than one edge for the same
a and
b.
Output
Output
k integer numbers in nondecreasing order — the lengths of the paths. In case there are less than
k different paths from
s to
t, output
NO
instead of the lengths of all nonexistent paths.
Example(s)
sample input

sample output

4 5 5
1 4
1 2 1
2 3 1
3 4 1
1 3 1
2 4 1

2
2
3
NO
NO

sample input

sample output

4 4 5
1 4
1 2 10
2 3 10
3 4 10
3 2 10

30
50
70
90
110

sample input

sample output

2 2 10
1 2
1 2 5
2 1 7

5
17
29
41
53
65
77
89
101
113
