Нислэгийн хөнгөлөлт

2s

512MB

1286

0%

Graph Algorithms

Сюрьялягаас Метсэля хүртэл хамгийн бага үнэтэй нислэгийн чиглэл ол. Нэг хөнгөлөлтийн тасалбар бий: үүгээр чиглэл дэх ямар ч нэг нислэгийн үнийг хагас болгож болно. Гэхдээ тасалбарыг зөвхөн нэг удаа хэрэглэж болно.

Үнэ нь $x$ байх нислэгт хөнгөлөлтийн тасалбар хэрэглэвэл үнэ нь $\lfloor x/2 \rfloor$ болно (бүхэл тоо руу доош багасгана).

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

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

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

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

Сюрьялягаас Метсэляд хүрэх боломж үргэлж байгаа гэж үзнэ.

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

Нэг бүхэл тоо хэвлэ: Сюрьялягаас Метсэля хүртэл хамгийн хямд чиглэлийн үнэ.

Хязгаарлалт

$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

Гаралт1

0.1 / 64 KiB

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