Đường Đi Ngắn Nhất II

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $n$ thành phố và $m$ con đường hai chiều giữa chúng. Cho $q$ truy vấn, mỗi truy vấn yêu cầu tìm độ dài đường đi ngắn nhất giữa hai thành phố cho trước.

Dữ liệu vào

Dòng 1: ba số nguyên $n$ , $m$ , $q$ .
$m$ dòng tiếp theo: mỗi dòng gồm ba số nguyên $a$ , $b$ , $c$ — con đường hai chiều giữa $a$ và $b$ với độ dài $c$ .
$q$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $a$ , $b$ — truy vấn khoảng cách ngắn nhất từ $a$ đến $b$ .

Dữ liệu ra

Với mỗi truy vấn, in khoảng cách ngắn nhất, hoặc $- 1$ nếu không tồn tại đường đi.

Ràng buộc

$1 \leq n \leq 500$
$1 \leq m \leq n^{2}$
$1 \leq q \leq 10^{5}$
$1 \leq c \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 3 5 1 2 5 1 3 9 2 3 3 1 2 2 1 1 3 1 4 3 2	5 5 8 -1 3	Từ 1 đến 3: qua 2 (5+3=8); 4 không kết nối.

Bình luận

Không có bình luận tại thời điểm này.