Илгээлт Хүргэлт

2s

512MB

1875

0%

Advanced Techniques

$n$ хот, нэг хотоос нөгөө рүү илгээлт тээвэрлэх боломжтой $m$ чиглэл байна. Чиглэл бүрийн хувьд илгээлтийн хамгийн их тоо, нэг илгээлтийн үнэ мэдэгдэнэ.

Syrjälä хотоос Lehmälä руу $k$ илгээлт илгээхийг хүсэж бай. Үүний хамгийн хямд аргыг ол.

https://cses.fi/problemset/task/2121

Оролтын формат

Эхний мөрөнд гурван бүхэл тоо $n$ , $m$ , $k$ байна: хот, чиглэл, илгээлтийн тоо. Хотууд $1,2,\dots,n$ -ээр дугаарлагдсан. $1$ дүгээр хот Syrjälä, $n$ дүгээр хот Lehmälä.

Дараагийн $m$ мөрөнд чиглэлүүд өгөгдөнө. Мөр бүрт дөрвөн бүхэл тоо $a$ , $b$ , $r$ , $c$ байна: $a$ хотоос $b$ хот руу чиглэл байга бөгөөд уг чиглэлээр хамгийн ихдээ $r$ илгээлт тээвэрлэж болох ба нэг илгээлтийн үнэ $c$ .

Гаралтын формат

Нэг бүхэл тоог хэвлэ: хамгийн бага нийт өртөг, шийд байхгүй бол $-1$ .

Хязгаарлалт

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

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...