Thoát khỏi mê cung
Đề bài
Mô tả
Jeremy tham gia một sự kiện của công ty và chơi một trò chơi: thoát khỏi một mê cung. Anh có trong tay bản đồ của mê cung.
Mê cung có phòng, đánh số từ đến . Jeremy xuất phát ở phòng , lối ra ở phòng .
Có lối đi hai chiều, mỗi lối đi nối hai phòng. Jeremy cần đơn vị thời gian để đi qua một lối đi bất kỳ (vào và ra khỏi phòng không mất thời gian). Jeremy có thể đứng yên trong một phòng bao lâu tùy ý.
Hệ thống của trò chơi sẽ đặt thêm một số lối đi vào một số thời điểm (vào lúc bắt đầu phút đó). Jeremy có thể đi qua một lối đi ngay sau khi nó được đặt.
Ví dụ, ban đầu mê cung có các lối đi , , , , và lối đi nối phòng với phòng được đặt vào phút thứ . Một cách đi tối ưu:
- Trong phút thứ nhất, Jeremy đi từ phòng sang phòng .
- Trong phút thứ hai, Jeremy đứng yên ở phòng .
- Vào đầu phút thứ ba, hệ thống đặt lối đi từ phòng sang phòng . Jeremy đi qua lối đi này ngay lập tức và tới phòng , lối ra.
Đáp án là phút.
Hãy xác định số phút ít nhất Jeremy cần để hoàn thành trò chơi.
Dữ liệu vào
- Dòng đầu tiên gồm hai số nguyên , (, ): số phòng và số lối đi ban đầu.
- dòng tiếp theo, dòng thứ gồm hai số nguyên , (): lối đi thứ nối phòng và phòng .
- Dòng thứ gồm một số nguyên (): số lối đi được đặt thêm.
- dòng tiếp theo, dòng thứ gồm ba số nguyên , , (, ): lối đi thứ được đặt vào phút thứ và nối phòng với phòng .
Dữ liệu ra
In ra một số nguyên: số phút ít nhất. In ra nếu Jeremy không thể hoàn thành trò chơi.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 4 1 2 3 4 2 3 5 4 1 3 2 5 |
3 | Đây là ví dụ được mô tả ở trên. |
| 4 3 3 1 1 2 2 3 1 10 1 4 |
10 | Jeremy không cần đi đâu cả: anh đứng ở phòng và đi sang phòng ngay khi lối đi được đặt vào phút thứ . |
Bình luận