Өндөр оноо

2s

512MB

1277

0%

Graph Algorithms

$n$ өрөө, $m$ тоннель бүхий тоглоом тоглож байна. Эхний оноо $0$ , тоннель бүр оноог $x$ -ээр нэмнэ; $x$ эерэг ч сөрөг ч байж болно. Тоннелийг хэдэн ч удаа дамжин өнгөрч болно.

$1$ дүгээр өрөөнөөс $n$ дүгээр өрөө рүү яв. Авч болох хамгийн их оноо нь юу вэ?

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

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

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

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

$1$ дүгээр өрөөнөөс $n$ дүгээр өрөөнд хүрэх боломжтой гэж үзнэ.

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

Нэг бүхэл тоо хэвлэ: авч болох хамгийн их оноо. Харин оноог хязгааргүй их болгож болох бол $-1$ хэвлэ.

Хязгаарлалт

$1 \le n \le 2500$
$1 \le m \le 5000$
$1 \le a,b \le n$
$-10^9 \le x \le 10^9$

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

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