Trạm cứu hộ
Đề bài
Mô tả
Công ty RYZ có trạm cứu hộ, được đánh số thứ tự từ đến . Các trạm được nối bởi tuyến đường hai chiều. Tuyến đường thứ nối trạm với trạm và có chiều dài . Từ một trạm luôn có thể đi đến mọi trạm khác, giữa hai trạm bất kỳ tồn tại đúng một đường đi.
Trung tâm chỉ huy cần lập phương án cho tình huống cứu hộ. Trong tình huống thứ có đội cứu hộ xuất phát từ các trạm có chỉ số là . Cần chọn một trạm trong trạm cứu hộ có sẵn làm trung tâm điều phối. Trạm được chọn có thể có hoặc không có đội cứu hộ xuất phát. Tất cả các đội cùng di chuyển tới trạm này và chi phí di chuyển của một đội bằng tổng chiều dài các tuyến đường trên đường đi của đội đó. Nếu một đội xuất phát ngay tại trung tâm điều phối thì chi phí của đội bằng . Tổng chi phí của tình huống bằng tổng chi phí di chuyển của tất cả các đội cứu hộ đến trung tâm điều phối.
Yêu cầu: với mỗi tình huống, hãy chọn trạm làm trung tâm điều phối sao cho tổng chi phí di chuyển của tất cả các đội là nhỏ nhất và đưa ra giá trị nhỏ nhất đó.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên dương lần lượt là số trạm cứu hộ và số tình huống cứu hộ (; ).
- Trong dòng tiếp theo, dòng thứ chứa ba số nguyên mô tả tuyến đường nối trạm và với độ dài (; ; ).
- Trong dòng tiếp theo, dòng thứ bắt đầu bằng số nguyên , sau đó là số nguyên mô tả các trạm xuất phát của những đội tham gia tình huống (). Các trạm này đôi một khác nhau và đều thuộc đoạn .
Dữ liệu bảo đảm tổng tất cả các nhỏ hơn hoặc bằng .
Dữ liệu ra
Gồm dòng, dòng thứ chứa tổng chi phí nhỏ nhất của tình huống thứ .
Ràng buộc
- , .
- .
- , .
Subtasks
- Subtask 1 ( số điểm): .
- Subtask 2 ( số điểm): .
- Subtask 3 ( số điểm): , với .
- Subtask 4 ( số điểm): , với .
- Subtask 5 ( số điểm): .
- Subtask 6 ( số điểm): Không có giới hạn gì thêm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 2 1 2 5 1 3 3 2 4 8 2 5 2 3 6 7 3 4 5 6 4 2 3 4 6 |
25 31 |
Tình huống (các trạm ): chọn trạm làm trung tâm, tổng chi phí nhỏ nhất là . |
| 5 3 1 2 4 2 3 1 3 4 6 3 5 2 2 1 4 3 1 4 5 1 5 |
11 13 0 |
Ví dụ thêm (không có trong đề gốc). Tình huống : chọn trạm (không có đội nào xuất phát ở đó), chi phí . Tình huống : đội duy nhất đã ở trung tâm. |
Bình luận