Giải bài trực tuyến

Công ty cung cấp dịch vụ mạng HDS vừa thiết lập một mạng truyền thông, mạng bao gồm n nút và m kênh nối trực tiếp một chiều giữa hai nút. Các nút được đánh số từ 1 đến n, các kênh nối được đánh số từ 1 đến m. Kênh nối thứ i cho phép truyền tin (một chiều) từ nút ui tới nút vi và có độ trễ là c(ui, vi). Có không quá một kênh truyền tin từ một nút đến một nút khác. Một đường truyền tin từ nút s đến nút t được biểu diễn dưới dạng một dãy liên tiếp các chỉ số của các nút, xuất phát từ s và kết thúc tại t. Độ trễ của đường truyền tin được định nghĩa là tổng độ trễ của các kênh nối trực tiếp trên đường truyền tin đó. Để đánh giá mạng truyền thông, công ty đưa ra kịch bản kiểm tra như sau: Ban đầu tất cả n nút đều ở chế độ không chuyển tiếp tin; có k thao tác thuộc một trong hai loại sau:

• Loại 1, nhận một chỉ số x (1 ≤ x ≤ n) có ý nghĩa: kích hoạt nút x sang chế độ được chuyển tiếp tin;
• Loại 2, nhận hai chỉ số x, y (1 ≤ x, y ≤ n) có ý nghĩa: cần tính độ trễ của đường truyền tin từ nút x đến nút y (không đi qua nút ở chế độ không chuyển tiếp tin) có độ trễ nhỏ nhất, nếu không tồn tại đường truyền thì đưa ra -1.

Yêu cầu: Cho biết mạng truyền thông của công ty HDS và kịch bản kiểm tra gồm k thao tác, hãy thực hiện lần lượt từng thao tác và với mỗi thao tác loại 2 thì đưa ra độ trễ nhỏ nhất cần tính.

Dữ liệu: Vào từ thiết bị vào chuẩn:

• Dòng đầu tiên chứa 3 số nguyên dương n, m, k;
• Dòng thứ i trong số m dòng tiếp theo ghi ba số nguyên dương ui, vi, c(ui, vi) lần lượt là chỉ số đầu, chỉ số cuối và độ trễ của kênh thứ i. Độ trễ của các kênh là nhỏ hơn 10^9.
• k dòng tiếp theo mô tả kịch bản, cụ thể:
  • Nếu thao tác thứ j thuộc loại 1 thì dòng thứ j gồm 2 số, số thứ nhất bằng 1 và số thứ hai là chỉ số nút;
  • Nếu thao tác thứ j thuộc loại 2 thì dòng thứ j gồm 3 số, số thứ nhất bằng 2 và hai số sau là hai chỉ số nút.

Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra thiết bị ra chuẩn một số dòng, mỗi dòng là câu trả lời cho thao tác loại 2 xuất hiện lần lượt trong kịch bản.

• Subtask 1 (20/70 điểm): Giả thiết có n ≤ 10, k ≤ 10.
• Subtask 2 (20/70 điểm): Giả thiết có n ≤ 100, k ≤ 10^2.
• Subtask 3 (30/70 điểm): Giả thiết có n ≤ 500, k ≤ 10^6.

Ví dụ:

Dữ liệu

4 5 5

1 4 1

1 3 5

1 2 1

4 3 1

2 3 2

2 1 3

1 2

2 1 3

1 4

2 1 3

Kết quả

5

3

2