Графын Замууд II

2s

512MB

1192

0%

Mathematics

$n$ орой, $m$ ирмэгтэй чиглэлт жинтэй граф өгөгдөнө. $1$ -р оройгоос $n$ -р орой хүртэл яг $k$ ирмэгтэй замын хамгийн бага уртыг ол.

Эх сурвалж: cses.fi

Эхний мөрөнд гурван бүхэл тоо $n$ , $m$ , $k$ байна: орой, ирмэгийн тоо ба замын урт. Оройгууд $1,2,\dots,n$ гэж дугаарлагдсан.

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

Замын хамгийн бага уртыг хэвлэ. Ийм зам байхгүй бол $-1$ хэвлэ.

Оролт1

Гаралт1

0.1 / 64 KiB

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