Мөрдөлт

2s

512MB

1346

0%

Graph Algorithms

Сюрьялягаас Лехмяля онгоцоор аялна. Дараах асуултуудад хариул:

ийм чиглэлийн хамгийн бага үнэ хэд вэ?
хамгийн бага үнэтэй чиглэл хэд байна вэ? ( $10^9+7$ -д хуваасан үлдэгдэл)
хамгийн бага үнэтэй чиглэл дэх нислэгийн хамгийн бага тоо хэд вэ?
хамгийн бага үнэтэй чиглэл дэх нислэгийн хамгийн их тоо хэд вэ?

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

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

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

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

Сюрьялягаас Лехмяля руу чиглэл байгаа гэж үзнэ.

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

Бодлогын нөхцөлд нийцүүлэн дөрвөн бүхэл тоо хэвлэ.

Хязгаарлалт

$1 \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

5 2 1 2

0.1 / 64 KiB

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