Khám phá hầm ngục
Đề bài
Mô tả
Alice và Bob phụ trách chạy thử một phòng thoát hiểm mới! Trong phòng thoát hiểm này, người chơi bị nhốt trong một hầm ngục và phải khám phá toàn bộ khu vực.
Hầm ngục gồm phòng được nối với nhau bởi đúng hành lang. Có thể đi giữa hai phòng bất kỳ bằng các hành lang này.
Hai trong số các phòng là phòng đặc biệt. Một phòng chứa một bảo vật hộ mệnh gọi là "chìa khoá xoắn". Một phòng khác chứa một "bẫy vòm" nguy hiểm: khi bẫy kích hoạt, người chơi không thể di chuyển nữa. Nếu đi vào phòng có bẫy trước khi lấy được chìa khoá, người chơi sẽ bị nhốt trong hầm ngục mãi mãi. Người chơi không bắt đầu ở phòng có chìa khoá hay phòng có bẫy.
Có tình huống khác nhau mà Alice và Bob muốn xem xét. Trong tình huống thứ , người chơi bắt đầu ở phòng , chìa khoá ở phòng và bẫy ở phòng . Với mỗi tình huống, hãy tính thời gian nhỏ nhất cần thiết để khám phá toàn bộ hầm ngục mà không bị mắc bẫy.
Dữ liệu vào
- Dòng đầu tiên gồm hai số nguyên và : số phòng và số tình huống cần xét. Các phòng được đánh số từ đến .
- dòng tiếp theo, mỗi dòng gồm ba số nguyên , , cho biết có một hành lang nối phòng và phòng (), đi qua hành lang này mất thời gian .
- dòng tiếp theo, dòng thứ gồm ba số nguyên đôi một khác nhau , , : phòng người chơi bắt đầu, phòng có chìa khoá và phòng có bẫy.
Dữ liệu ra
Với mỗi tình huống, in ra trên một dòng thời gian nhỏ nhất cần thiết để đi qua mọi phòng ít nhất một lần. Nếu không thể đi qua mọi phòng, in ra impossible.
Ràng buộc
- , .
- , , .
- , ba số , , đôi một khác nhau.
Ví dụ
Hầm ngục của ví dụ thứ nhất (số trên cạnh là thời gian đi qua hành lang):
graph weighted 1 2 3 1 3 1 3 4 4 3 5 2
| Input | Output | Giải thích |
|---|---|---|
| 5 4 1 2 3 1 3 1 3 4 4 3 5 2 1 2 4 1 4 2 5 2 1 4 3 1 |
15 17 impossible 12 |
Tình huống 1: đi , mất . Tình huống 2: phải lấy chìa khoá ở phòng trước khi vào phòng , đi , mất . Tình huống 3: mọi đường từ phòng tới phòng đều qua phòng có bẫy. Tình huống 4: đi , mất . |
| 7 4 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 1 7 1 1 2 3 5 4 1 3 1 4 2 4 5 |
11 impossible 10 10 |
Hình sao tâm , mọi hành lang dài . Tình huống 2: bẫy ở tâm , không thể tới phòng có chìa khoá. Tình huống 3: đi từ phòng qua tâm (lấy chìa khoá), thăm lần lượt các phòng lá còn lại và dừng ở phòng lá cuối cùng, mất . |
Bình luận