MST khi bắt buộc dùng một cạnh

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

Kỹ sư cần đánh giá q kịch bản. Mỗi kịch bản bắt buộc phải đưa một cạnh đã có vào cây khung, sau đó vẫn muốn tổng chi phí nhỏ nhất có thể.

Yêu cầu

Với mỗi chỉ số cạnh được hỏi, tính chi phí nhỏ nhất của một cây khung chứa cạnh đó. Nếu không tồn tại cây khung, in -1.

Input

Dòng đầu n, m, q; m dòng tiếp theo là u, v, w theo thứ tự 1..m; sau đó q dòng, mỗi dòng là chỉ số cạnh bắt buộc.

Output

Mỗi truy vấn in một chi phí hoặc -1.

Ràng buộc

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

Ví dụ 1

Input

4 5 3
1 2 1
2 3 2
3 4 3
1 4 10
1 3 4
1
4
5

Output

6
13
8

Giải thích. Cạnh được hỏi được union trước; phần còn lại do Kruskal chọn tối ưu dưới ràng buộc đó.

Ví dụ 2

Input

3 1 1
1 2 5
1

Output

-1

Giải thích. Cạnh được hỏi được union trước; phần còn lại do Kruskal chọn tối ưu dưới ràng buộc đó.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from Codeforces 609E – Minimum spanning tree for each edge. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.