Các Tuyến Bay

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $n$ thành phố và $m$ chuyến bay một chiều. Tìm $k$ đường đi có chi phí nhỏ nhất từ thành phố $1$ đến thành phố $n$ (đường đi có thể đi qua một thành phố nhiều lần, các đường có chi phí bằng nhau được tính riêng).

Dữ liệu vào

Dòng 1: ba số nguyên $n$ , $m$ , $k$ .
$m$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $a$ , $b$ , $c$ — chuyến bay từ $a$ đến $b$ với chi phí $c$ .

Dữ liệu ra

In $k$ số nguyên — chi phí của $k$ đường đi ngắn nhất theo thứ tự tăng dần.

Ràng buộc

$2 \leq n \leq 10^{5}$
$1 \leq m \leq 2 \times 10^{5}$
$1 \leq k \leq 10$
$1 \leq c \leq 10^{9}$
Đảm bảo tồn tại ít nhất $k$ đường đi từ $1$ đến $n$ .

Ví dụ

Input	Output	Giải thích
4 6 3 1 2 1 1 3 3 2 3 2 2 4 6 3 2 8 3 4 1	4 4 7	Ba đường đi rẻ nhất: 1→3→4 (4), 1→2→3→4 (4), 1→2→4 (7).

Bình luận

Không có bình luận tại thời điểm này.