## Khuyên thật nên động não trước khi đọc đáp đi!
Tương tự như bài [Rừng tre lạc Lối](https://marisaoj.com/problem/122) khi mà ta sẽ tìm đường đi ngắn
nhất có số cạnh chia hết cho $2$ bằng $BFS$, bài này là dạng tổng quát khi yêu cầu tìm đường đi ngắn nhất chia hết cho số $k$ cho trước.
Ta sẽ tạo một mảng đếm $2$ chiều để lưu số cạnh đường đi kèm với số dư của nó khi chia cho $k$:
$\color{lime}{\textbf{vector}}\color{red}{<}\color{lime}{\textbf{vector}}
\color{red}{<}\color{blue}{\textbf{int}}\color{red}{>>}f\color{red}{(}n\color{red}{+}
\color{violet}{1}\color{red}{,}\color{lime}{\textbf{vector}}
\color{red}{<}\color{blue}{\textbf{int}}\color{red}{>(}k\color{red}{,-}k\color{red}{));}$
Từ $0$ đến $k - 1$ là số dư của số cạnh khi chia cho $k$.
Còn với hàng đợi sẽ là:
$\color{lime}{\textbf{queue}}\color{red}{<}\color{lime}{\textbf{pair}}
\color{red}{<}\color{blue}{\textbf{int}}\color{red}{,}\color{blue}{\textbf{int}}\color{red}{>>}
q\color{red}{;}$
để thực hiện BFS kèm trạng thái chia cho $k$ của nó.
Mỗi lần $BFS$ thêm $1$ cạnh thì chuyển số dư của nó là $r$ thành $(r+1)$%$k$.
Đáp án sẽ là $f[n][0]/k$.
$Bonus:$
- Mảng $f$ được gán tất cả giá trị là $-k$ để in ra $f[n][0]/k$ luôn cho gọn, không mất công $if$.
minhnhatha
Created at
4 likes