Mê cung chìa khóa
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Một mê cung gồm $N$ căn phòng đánh số từ $1$ đến $N$ và $M$ hành lang hai chiều. Có $K$ loại chìa khóa khác nhau đánh số từ $0$ đến $K - 1$.
Tại mỗi phòng $i$, có một tập hợp các chìa khóa được biểu diễn bằng một mặt nạ bit key_at[i] ($0 \le \text{key_at}[i] < 2^K$). Khi bạn bước vào phòng $i$, bạn tự động nhặt tất cả các chìa khóa ở phòng đó.
Mỗi hành lang nối $u$ và $v$ có một ổ khóa yêu cầu mặt nạ bit req ($0 \le \text{req} < 2^K$): bạn chỉ có thể đi qua hành lang này nếu tập chìa khóa bạn đang giữ chứa tất cả các bit trong req (tức là (mask & req) == req).
Bạn xuất phát ở phòng $1$ (đã nhặt chìa khóa tại phòng $1$) và muốn đến phòng $N$. Hãy tìm số lượng hành lang ít nhất cần đi qua, hoặc in ra -1 nếu không thể.
Dữ liệu vào
- Dòng đầu chứa ba số nguyên $N, M, K$ ($1 \le N \le 1000$, $0 \le M \le 3000$, $0 \le K \le 10$).
- Dòng thứ hai chứa $N$ số nguyên
key_at[1..N]($0 \le \text{key_at}[i] < 2^K$). - $M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, \text{req}$ ($1 \le u, v \le N$, $0 \le \text{req} < 2^K$).
Dữ liệu ra
- Một số nguyên duy nhất là số bước ít nhất từ $1$ đến $N$, hoặc
-1nếu không thể.
Ví dụ
| Input | Output |
|---|---|
| 4 4 2 0 1 2 0 1 2 0 1 3 1 2 4 3 3 4 1 |
4 |
| 3 2 1 0 0 1 1 2 0 2 3 1 |
-1 |
Giới hạn
- $1 \le N \le 1000$, $0 \le M \le 3000$, $0 \le K \le 10$.
Community Discussion