Giao Hàng

Đ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$ tuyến đường. Bạn cần vận chuyển $k$ kiện hàng từ thành phố $1$ đến thành phố $n$ .

Mỗi tuyến đường từ thành phố $a$ đến thành phố $b$ có thể vận chuyển tối đa $r$ kiện hàng, và chi phí vận chuyển là $c$ đồng cho mỗi kiện. Hãy tìm tổng chi phí vận chuyển nhỏ nhất để chuyển đủ $k$ kiện hàng.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $n$ , $m$ , $k$ — số thành phố, số tuyến đường, và số kiện hàng cần vận chuyển.

$m$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $a$ , $b$ , $r$ , $c$ — mô tả tuyến đường từ $a$ đến $b$ với sức chứa tối đa $r$ kiện và chi phí $c$ đồng/kiện.

Dữ liệu ra

In một số nguyên duy nhất là tổng chi phí vận chuyển nhỏ nhất, hoặc $- 1$ nếu không thể vận chuyển đủ $k$ kiện hàng.

Ràng buộc

$2 \leq n \leq 500$
$1 \leq m \leq 1000$
$1 \leq k \leq 100$
$1 \leq a, b \leq n$
$1 \leq r, c \leq 1000$

Ví dụ

Input	Output	Giải thích
4 5 3 1 2 5 100 1 3 10 50 1 4 7 500 2 4 8 350 3 4 2 100	750	1 kiện đi qua đường 1→2→4 (chi phí 450), 2 kiện đi qua đường 1→3→4 (chi phí 300). Tổng: 750.
2 1 5 1 2 3 10	-1	Tuyến duy nhất chỉ chứa được 3 kiện, không đủ để vận chuyển 5 kiện.

Bình luận

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