Татан авалтын хурд

2s

512MB

1474

0%

Graph Algorithms

$n$ компьютер, $m$ холбоо бүхий сүлжээ өгөгдөв. Холбоо тус бүр нэг компьютер нөгөө рүү нь өгөгдөл ямар хурдтай илгээхийг тодорхойлно.

Котивало серверээс өгөгдөл татан авахыг хүсэж байгаа. Сүлжээний холбоонуудыг ашиглан татан авалтын хамгийн их хурдыг ол.

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

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

Эхний мөрөнд хоёр бүхэл тоо $n$ ба $m$ : компьютерүүд болон холбоонуудын тоо. Компьютерүүд $1,2,\dots,n$ гэж дугаарлагдсан. Компьютер $1$ нь сервер, компьютер $n$ нь Котивалогийн компьютер.

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

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

Нэг бүхэл тоо хэвлэ: Котивалогийн татан авах өгөгдлийн хамгийн их хурд.

Хязгаарлалт

$1 \le n \le 500$
$1 \le m \le 1000$
$1 \le a,b \le n$
$1 \le c \le 10^9$

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

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