Mê cung chìa khóa

Buổi 24 — Mock Contest Phase 1
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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 -1 nế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$.
Draft saved