Ялгаатай Чиглэлүүд II

2s

512MB

1900

0%

Advanced Techniques

Тоглоом нь $n$ өрөө, $m$ телепортоос тогтоно. Өдөр бүрийн эхэнд өрөө $1$ -ээс эхлээд өрөө $n$ -д хүрэх ёстой.

Тоглоомын турш телепорт бүрийг хамгийн ихдээ нэг удаа ашиглаж болно. Яг $k$ өдөр тоглохыг хүсэж бай. Телепорт ашиглах бүрд нэг зоос төлнө. Оновчтой тогловол $k$ өдөрт төлөх хамгийн бага зоосны тоог ол.

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

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

Эхний мөрөнд гурван бүхэл тоо $n$ , $m$ , $k$ байна: өрөө, телепорт, тоглох өдрийн тоо. Өрөөнүүд $1,2,\dots,n$ -ээр дугаарлагдсан.

Дараагийн $m$ мөрөнд телепортууд өгөгдөнө. Мөр бүрт хоёр бүхэл тоо $a$ , $b$ байна: өрөө $a$ -аас өрөө $b$ руу телепорт байна.

Ижил эхлэл, төгсгөлийн өрөөтэй хоёр телепорт байхгүй.

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

Эхлээд нэг бүхэл тоог хэвлэ: оновчтой тогловол төлөх хамгийн бага зоосны тоо. Дараа нь жишээтэй адил хэлбэрээр $k$ чиглэлийг хэвлэ. Ямар ч хүчинтэй шийдийг хэвлэж болно.

$k$ өдөр тоглох боломжгүй бол зөвхөн -1 хэвлэ.

Хязгаарлалт

$2 \le n \le 500$
$1 \le m \le 1000$
$1 \le k \le n-1$
$1 \le a,b \le n$

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

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