Cho một đồ thị vô hướng gồm n đỉnh, được đánh số từ 1 đến n. Mỗi cạnh có một độ dài nguyên dương. Bạn cần trả lời q truy vấn độc lập; mỗi truy vấn hỏi độ dài đường đi ngắn nhất giữa hai đỉnh cho trước.
Nếu hai đỉnh thuộc hai thành phần liên thông khác nhau thì không tồn tại đường đi giữa chúng.
Input
Dòng đầu chứa ba số nguyên n,m và q - số đỉnh, số cạnh và số truy vấn.
Mỗi dòng trong m dòng tiếp theo chứa ba số nguyên a,b,c, biểu thị một cạnh vô hướng nối a với b, có độ dài c.
Mỗi dòng trong q dòng cuối chứa hai số nguyên a,b, yêu cầu khoảng cách ngắn nhất từ a tới b.
Output
Với mỗi truy vấn, in đáp án trên một dòng. Nếu không có đường đi, in −1.
Constraints
1≤n≤500.
1≤m≤n2.
1≤q≤105.
1≤a,b≤n.
1≤c≤109.
Có thể có khuyên và nhiều cạnh nối cùng một cặp đỉnh.
Scoring
Subtask 1 (50% số điểm): n≤30,m≤200 và q≤50.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Giải thích: Cạnh độ dài 3 giữa 1 và 2 cho đường 1−2−3−4 có tổng độ dài 9, còn đỉnh 5 không nối với đỉnh nào. Khoảng cách từ một đỉnh tới chính nó bằng 0.
Lời giải tóm tắt
Phân tích: Số đỉnh chỉ tới 500, trong khi số truy vấn có thể rất lớn. Vì vậy ta tính trước khoảng cách ngắn nhất cho mọi cặp đỉnh bằng Floyd-Warshall, rồi trả lời mỗi truy vấn trong O(1).
Thuật toán: Khởi tạo dist[i][i] = 0, các ô khác bằng vô cùng. Với mỗi cạnh vô hướng, cập nhật cả dist[a][b] và dist[b][a] bằng trọng số nhỏ nhất đã gặp.
Thuật toán: Lần lượt cho phép đỉnh k = 1..n làm đỉnh trung gian. Với mọi i, j, cập nhật
Thuật toán:dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
Thuật toán: Cuối cùng, mỗi truy vấn dùng trực tiếp một ô của ma trận; ô vô cùng được in là -1.
Chứng minh tính đúng đắn: Sau khi xử lý các đỉnh trung gian từ 1 tới k, dist[i][j] là độ dài nhỏ nhất của một đường từ i tới j chỉ dùng các đỉnh trong tập 1..k làm trung gian. Mệnh đề đúng ban đầu khi chưa có đỉnh trung gian. Khi thêm k, một đường tối ưu hoặc không đi qua k, hoặc tách được thành đường i -> k và k -> j; công thức cập nhật lấy đúng trường hợp tốt hơn. Với k = n, mọi đường hợp lệ đều đã được xét.