Đường ống sữa

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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

Mạng ống gồm $N$ điểm nối và $M$ ống hai chiều. Mỗi ống có độ trễ $L$ (thời gian sữa đi qua) và công suất $C$ (lưu lượng tối đa). Độ trễ của một đường đi = tổng $L$ các ống. Công suất = min $C$ các ống.

Cần bơm $X$ đơn vị sữa từ điểm $1$ đến điểm $N$ qua một đường đi. Thời gian = độ trễ + $X$ /công suất.

Tìm đường đi có thời gian nhỏ nhất, làm tròn xuống.

Dữ liệu vào

Dòng $1$ : Ba số nguyên $N$ , $M$ , $X$ ( $1 \leq N \leq 500$ , $1 \leq M \leq 500$ , $1 \leq X \leq 10^{6}$ ).
$M$ dòng tiếp: Bốn số nguyên $I$ , $J$ , $L$ , $C$ — ống nối $I$ và $J$ với độ trễ $L$ và công suất $C$ ( $1 \leq L, C \leq 10^{6}$ ).

Dữ liệu ra

Một số nguyên — thời gian nhỏ nhất (làm tròn xuống).

Ràng buộc

$1 \leq N \leq 500$ , $1 \leq M \leq 500$ , $1 \leq X \leq 10^{6}$
$1 \leq L, C \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
3 3 15 1 2 10 3 3 2 10 2 1 3 14 1	27	Đường 1→2→3: trễ=20, công suất=2, thời gian=20+15/2=27.5→27. Tốt hơn đường 1→3 (thời gian 29).

Bình luận

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