Хамгийн богино чиглэл II

2s

512MB

1269

0%

Graph Algorithms

$n$ хот, тэдгээрийн хооронд $m$ зам бий. Өгөгдсөн хоёр хотын хоорондох хамгийн богино чиглэлийн уртыг тодорхойлох $q$ хүсэлтийг боловсруул.

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

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

Эхний мөрөнд $n$ , $m$ , $q$ гурван бүхэл тоо байна: хот, зам, хүсэлтийн тоо.

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

Төгсгөлд нь хүсэлтүүдийг тодорхойлсон $q$ мөр байна. Мөр бүрт $a$ ба $b$ хоёр бүхэл тоо байна: $a$ ба $b$ хотуудын хоорондох хамгийн богино чиглэлийн уртыг тодорхойл.

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

Хүсэлт бүрт хамгийн богино чиглэлийн уртыг хэвлэ. Чиглэл байхгүй бол оронд нь $-1$ хэвлэ.

Хязгаарлалт

$1 \le n \le 500$
$1 \le m \le n^2$
$1 \le q \le 10^5$
$1 \le a,b \le n$
$1 \le c \le 10^9$

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

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