Нислэгийн чиглэлүүд

2s

512MB

1303

0%

Graph Algorithms

Сюрьялягаас Метсэля хүртэл хамгийн хямд $k$ чиглэлийг ол. Чиглэл нэг хотод хэдэн ч удаа очиж болно.

Ижил үнэтэй хэд хэдэн чиглэл байж болох бөгөөд тэдгээрийг бүгдийг тооцно (жишээг хар).

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

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

Эхний мөрөнд $n$ , $m$ , $k$ гурван бүхэл тоо байна: хот, нислэгийн тоо ба параметр $k$ . Хотууд $1,2,\ldots,n$ гэж дугаарлагдсан. 1 дүгээр хот Сюрьяля, $n$ дүгээр хот Метсэля.

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

Сюрьялягаас Метсэля хүртэл хаяж $k$ ялгаатай чиглэл байгаа гэж үзнэ.

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

$k$ бүхэл тоо хэвлэ: үнээр нь эрэмбэлсэн $k$ хамгийн хямд чиглэлийн үнүүд.

Хязгаарлалт

$2 \le n \le 10^5$
$1 \le m \le 2 \cdot 10^5$
$1 \le a,b \le n$
$1 \le c \le 10^9$
$1 \le k \le 10$

Жишээ

Оролт1

Гаралт1

4 4 7

0.1 / 64 KiB

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