CSES - Flight Routes | Lộ trình bay

View as PDF

Submit solution

Points: 1700 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Authors:
Problem type

Nhiệm vụ của bạn là tìm ~k~ lộ trình bay ngắn nhất từ Syrjälä đến Metsälä. Một lộ trình có thể đi qua một thành phố vài lần.

Lưu ý rằng có thể có một số lộ trình với cùng một mức giá và mỗi lộ trình nên được xét (xem ví dụ).

Input

  • Dòng đầu vào đầu tiên có ba số nguyên ~n~, ~m~, và ~k~: số lượng thành phố, chuyến bay, và tham số ~k~. Các thành phố được đánh số ~1, 2, \ldots, n~. Thành phố ~1~ là Syrjälä, và thành phố ~n~ là Metsälä.
  • Sau này, có ~m~ dòng mô tả các chuyến bay. Mỗi dòng có ba số nguyên ~a~, ~b~, và ~c~: chuyến bay bắt đầu tại thành phố ~a~, kết thúc tại thành phố ~b~, và giá của nó là ~c~. Tất cả các chuyến bay đều là chuyến bay một chiều.
  • Bạn có thể giả định rằng có ít nhất ~k~ lộ trình phân biệt từ Syrjälä đến Metsälä.

Output

  • In ~k~ số nguyên: giá của ~k~ tuyến đường rẻ nhất được sắp xếp theo giá của chúng.

Constraints

  • ~2 \le n \le 10^5~
  • ~1 \le m \le 2 \cdot 10^5~
  • ~1 \le a,b \le n~
  • ~1 \le c \le 10^9~
  • ~1 \le k \le 10~

Example

Sample input

4 6 3
1 2 1
1 3 3
2 3 2
2 4 6
3 2 8
3 4 1

Sample output

4 4 7

Note

Các lộ trình rẻ nhất là ~1 \rightarrow 3 \rightarrow 4~ (giá là ~4~), ~1 \rightarrow 2 \rightarrow 3 \rightarrow 4~ (giá là ~4~) và ~1 \rightarrow 2 \rightarrow 4~ (giá là ~7~).

LQDOJ's license
Be the first to comment

Comments

There are no comments at the moment.