Bảng tuyến đường toàn cục

Bối cảnh và bài toán

Một mạng nhỏ có nhiều truy vấn hỏi khoảng cách ngắn nhất giữa hai nút bất kỳ. Các cạnh là hai chiều và trọng số dương.

Yêu cầu

Trả lời q truy vấn khoảng cách ngắn nhất.

Input

Dòng đầu n, m, q; tiếp theo m cạnh u, v, w; sau đó q cặp a, b.

Output

Mỗi truy vấn in khoảng cách hoặc -1 nếu không có đường.

Ràng buộc

• 1 <= n <= 500
• 0 <= m <= n*(n-1)/2
• 1 <= q <= 10^5
• 1 <= w <= 10^9 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 80, q <= 200 | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

4 3 4
1 2 5
1 3 9
2 3 3
1 3
1 4
2 3
4 4

Output

8
-1
3
0

Giải thích. Floyd-Warshall tiền xử lý mọi cặp, sau đó mỗi truy vấn chỉ đọc một ô của ma trận khoảng cách.

Ví dụ 2

Input

2 1 2
1 2 7
1 2
2 2

Output

7
0

Giải thích. Floyd-Warshall tiền xử lý mọi cặp, sau đó mỗi truy vấn chỉ đọc một ô của ma trận khoảng cách.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Shortest Routes II. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.