The PDF version of this problem can be downloaded here.
The Pizza Festival is near! Every city has to send a pizza to the capital city in order to
glorify the king. As a mayor, Tomato the Great has prepared a specially flavored pizza
- milk-tea pizza! Then, he demands you to take this pizza to the capital city.
You would like to find the safest path to the capital city. But since you need to
arrive the capital city before the festival, you cannot spend too long time on the way.
Thus, you only want to consider the top-k shortest paths from your city to the capital
city.
Now, given the map, please find out top-k shortest paths. Note that you do not mind to pass through a city more than once.
The first line of the input le contains an integer T (1 ≤ T ≤ 15) indicating the number of test cases.
The first line of each test case contains three integers, n, m, and k (2 ≤ n ≤ 10000,
2 ≤ m ≤ 50000, k ≤ 10000), denoting the number of cities, the number of roads, and
the number of shortest paths you want. The next line contains two integers, s and t,
denoting the city you are in and the capital city. Each of the following m lines contains
three integers, xi, yi, and vi, denoting a road from xi to yi which length is vi(1 ≤ vi ≤ 1000).
The input guarantees that there is at least k paths from your city to the capital city.
For each test case please output the length of top-k shortest paths in ascending order,
each on one line.
2 4 4 4 1 4 1 2 10 2 3 10 3 4 10 3 2 10 2 2 5 1 2 1 2 5 2 1 7
30 50 70 90 5 17 29 41 53
Migrated from old NTUJ.
sgu314
| No. | Testdata Range | Score |
|---|